<HTML>
<HEAD>
<TITLE>FastDB Main Memory Database Management System</TITLE>
<UL>
<LI> <A HREF = "#introduction">Introduction</A>
<LI> <A HREF = "#sql">Query language</A>
  <UL>
  <LI> <A HREF = "#structure">Structures</A>
  <LI> <A HREF = "#array">Arrays</A>
  <LI> <A HREF = "#string">Strings</A>
  <LI> <A HREF = "#reference">References</A>
  <LI> <A HREF = "#rectangle">Rectangle</A>
  <LI> <A HREF = "#function">Functions</A>
  </UL>
<LI> <A HREF = "#cpp">C++ interface</A>
  <UL>
  <LI> <A HREF = "#table">Table</A>
  <LI> <A HREF = "#query">Query</A>
  <LI> <A HREF = "#cursor">Cursor</A>
  <LI> <A HREF = "#database">Database</A>
  </UL>
<LI> <A HREF = "#cli">CLI - call level interface</A>
  <UL>
  <LI> <A HREF = "#cli_errors">CLI error codes</A>
  <LI> <A HREF = "#cli_types">CLI supported types</A>
  <LI> <A HREF = "#cli_open">cli_open</A>
  <LI> <A HREF = "#cli_close">cli_close</A>
  <LI> <A HREF = "#cli_statement">cli_statement</A>
  <LI> <A HREF = "#cli_parameter">cli_parameter</A>
  <LI> <A HREF = "#cli_column">cli_colunm</A>
  <LI> <A HREF = "#cli_array_column">cli_array_column</A>
  <LI> <A HREF = "#cli_fetch">cli_fetch</A>
  <LI> <A HREF = "#cli_insert">cli_insert</A>
  <LI> <A HREF = "#cli_get_first">cli_get_first</A>
  <LI> <A HREF = "#cli_get_last">cli_get_last</A>
  <LI> <A HREF = "#cli_get_next">cli_get_next</A>
  <LI> <A HREF = "#cli_get_prev">cli_get_prev</A>
  <LI> <A HREF = "#cli_get_oid">cli_get_oid</A>
  <LI> <A HREF = "#cli_update">cli_update</A>
  <LI> <A HREF = "#cli_remove">cli_remove</A>
  <LI> <A HREF = "#cli_close_cursor">cli_close_cursor</A>
  <LI> <A HREF = "#cli_free">cli_free</A>
  <LI> <A HREF = "#cli_commit">cli_commit</A>
  <LI> <A HREF = "#cli_abort">cli_abort</A>
  <LI> <A HREF = "#cli_show_tables">cli_show_tables</A>
  <LI> <A HREF = "#cli_describe">cli_describe</A>
  <LI> <A HREF = "#cli_describe_layout">cli_describe_layout</A>
  <LI> <A HREF = "#cli_create_table">cli_create_table</A>
  <LI> <A HREF = "#cli_alter_table">cli_alter_table</A>
  <LI> <A HREF = "#cli_drop_table">cli_drop_table</A>
  <LI> <A HREF = "#cli_alter_index">cli_alter_index</A>
  <LI> <A HREF = "#cli_freeze">cli_freeze</A>
  <LI> <A HREF = "#cli_unfreeze">cli_unfreeze</A>
  <LI> <A HREF = "#cli_seek">cli_seek</A>
  <LI> <A HREF = "#cli_skip">cli_skip</A>
  </UL>
<LI> <A HREF = "#localcli">Local implementation of CLI</A>
  <UL>
  <LI> <A HREF = "#cli_create">cli_create</A>
  <LI> <A HREF = "#cli_create_replication_node">cli_create_replication_node</A>
  <LI> <A HREF = "#cli_attach">cli_attach</A>
  <LI> <A HREF = "#cli_detach">cli_detach</A>
  <LI> <A HREF = "#cli_create_transaction_context">cli_create_transaction_context</A>
  <LI> <A HREF = "#cli_join_transaction">cli_join_transaction</A>
  <LI> <A HREF = "#cli_remove_transaction_context">cli_remove_transaction_context</A>
  <LI> <A HREF = "#cli_get_database_state">cli_get_database_state</A>
  <LI> <A HREF = "#cli_prepare_query">cli_prepare_query</A>
  <LI> <A HREF = "#cli_execute_query">cli_execute_query</A>
  <LI> <A HREF = "#cli_execute_query_ex">cli_execute_query_ex</A>
  <LI> <A HREF = "#cli_insert_struct">cli_insert_struct</A>
  <LI> <A HREF = "#cli_xml_export">cli_xml_export</A>
  <LI> <A HREF = "#cli_xml_import">cli_xml_import</A>
  </UL>
<LI> <A HREF = "jnicli/docs/index.html">Native interface to Java language</A>
<LI> <A HREF = "#advanced">Delayed transactions and online backup scheduler</A>
<LI> <A HREF = "#replication">Fault tolerant support</A>
<LI> <A HREF = "#optimization">Query optimization</A>
  <UL>
  <LI> <A HREF = "#indices">Using indices in queries</A>
  <LI> <A HREF = "#inverse">Inverse references</A>
  <LI> <A HREF = "#realtime">Realtime issues</A>
  <LI> <A HREF = "#par">Parallel query execution</A>
  </UL>
<LI> <A HREF = "#gist">Generalized search tree</A>
<LI> <A HREF = "#implementation">FastDB implementation issues</A>
  <UL>
  <LI> <A HREF = "#memory">Memory allocation</A>
  <LI> <A HREF = "#transaction">Transactions</A>
  <LI> <A HREF = "#recovery">Recovery</A>
  <LI> <A HREF = "#hashtable">Hash table</A>
  <LI> <A HREF = "#ttree">T-tree</A>
  </UL>
<LI> <A HREF = "#subsql">Interactive SQL</A>
<LI> <A HREF = "#www">API for development Web applications</A>
<LI> <A HREF = "#examples">Examples of FastDB applications</A>
  <UL>
  <LI> <A HREF = "#guess">Example: game "Guess an animal"</A>
  <LI> <A HREF = "#testdb">Example: various types of queries</A>
  <LI> <A HREF = "#testperf">Performance test</A>
  <LI> <A HREF = "#bugdb">Bug tracking database</A>
  <LI> <A HREF = "#clidb">Clients-Managers database</A>
  </UL>
<LI> <A HREF = "#quick">Quick start</A>
<LI> <A HREF = "#dbsize">Reducing initial size of the database file</A>
<LI> <A HREF = "#diskless">Diskless configuration</A>
<LI> <A HREF = "#sharing">Sharing of classes between different databases</A>
<LI> <A HREF = "docs/html/index.html">Documentation generated by Doxygen</A>
<LI> <A HREF = "#distribution">Distribution terms</A>
</UL>

<BODY>
<HR>
<H2><A NAME = "introduction">Introduction</A></H2>

FastDB is a highly efficient main memory database system 
with realtime capabilities and convenient C++ interface.
FastDB doesn't support a client-server architecture and all applications
using a FastDB database should run at the same host. FastDB is optimized 
for applications with dominated read access pattern. High speed of query 
execution is provided by the elimination of data transfer overhead and
a very effective locking implementation. The Database file is mapped to the virtual
memory space of each application working with the database. So the query is executed in
the context of the application, requiring no context switching and data transfer.
Synchronization of concurrent database access is implemented in FastDB 
by means of atomic instructions, adding almost 
no overhead to query processing. FastDB assumes that the whole database is 
present in RAM and optimizes the search algorithms and structures according to this
assumption. Moreover, FastDB has no overhead caused by database buffer management
and needs no data transfer between a database file and buffer pool. 
That is why FastDB 
will work significantly faster than a traditional database with all data cached 
in buffers pool.<P>

FastDB supports transactions, online backup and automatic recovery 
after system crash. The transaction commit protocol is based on
a shadow root pages algorithm, performing atomic update of the database.
Recovery can be done very fast, providing 
high availability for critical applications. Moreover, the elimination
of transaction logs improves the total system performance and leads to a more 
effective usage of system resources.<P>

FastDB is an application-oriented database. Database tables are constructed using
information about application classes. FastDB supports automatic scheme 
evaluation, allowing you to do changes only in one place - in your
application classes. FastDB provides a flexible and convenient interface
for retrieving data from the database. A SQL-like query language is used
to specify queries. Such post-relational capabilities as non-atomic
fields, nested arrays, user-defined types and methods, direct interobject 
references simplifies the design of database applications and makes them more
efficient.<P>

Although FastDB is optimized in the assumption that database as a whole fits
into the physical memory of the computer, it is also possible to use it with databases,
the size of which exceeds the size of the physical memory in the system. In the last 
case, standard operating system swapping mechanisms will work. But 
all FastDB search algorithms and structures are optimized under the assumption of
residence of all data in memory, so the efficiency for swapped 
out data will not be very high.<P> 


<H2><A NAME = "sql">Query language</A></H2>

FastDB supports a query language with SQL-like syntax. FastDB uses a notation more
popular for object-oriented programming then for a relational database. 
Table rows are considered as object instances, the table is the class of these
objects. Unlike SQL, FastDB is oriented on work with objects instead of SQL
tuples. So the result of each query execution  is a set of objects of one 
class. The main differences of the FastDB query language from standard SQL are:<P>

<OL>
<LI> There are no joins of several tables and nested subqueries. The query always
returns a set of objects from one table. 
<LI> Standard C types are used for atomic table columns.
<LI> There are no NULL values, except null references. 
I completely agree with C.J. Date's criticism of three-value logic and his 
proposal to use default values instead. 
<LI> Structures and arrays can be used as record components. A special 
<B>exists</B> quantor is provided for locating elements in arrays. 
<LI> Parameterless user methods can be defined for table records (objects) as well as
for record components.
<LI> User functions with (only) one single string or numeric argument can be defined by
the application. 
<LI> References between objects are supported including automatic support
for inverse references. 
<LI>Construction of <code>start from follow by</code> performs a recursive records
traversal using references.
<LI> Because the query language is deeply integrated into C++ classes, a case
sensitive mode is used for language identifiers as well as for keywords. 
<LI> No implicit conversion of integer and floating types to string
representation is done. If such conversion is needed, it must be done explicitly. 
</OL><P>

The following rules in BNF-like notation specify the grammar of the
FastDB query language search predicates:<P>

<TABLE BORDER ALIGN="center">
<CAPTION>Grammar conventions</CAPTION>
<TR><TH>Example</TH><TH>Meaning</TH></TR>
<TR><TD><I>expression</I></TD><TD>non-terminals</TD></TR>
<TR><TD><B>not</B></TD><TD>terminals</TD></TR>
<TR><TD ALIGN="center">|</TD><TD>disjoint alternatives</TD></TR>
<TR><TD>(<B>not</B>)</TD><TD>optional part</TD></TR>
<TR><TD>{<B>1</B>..<B>9</B>}</TD><TD>repeat zero or more times</TD></TR>
</TABLE><P>

<PRE>
<I>select-condition</I> ::= ( <I>expression</I> ) ( <I>traverse</I> ) ( <I>order</I> )
<I>expression</I> ::= <I>disjunction</I>
<I>disjunction</I> ::= <I>conjunction</I> 
        | <I>conjunction</I> <B>or</B> <I>disjunction</I>
<I>conjunction</I> ::= <I>comparison</I> 
        | <I>comparison</I> <B>and</B> <I>conjunction</I>
<I>comparison</I> ::= <I>operand</I> <B>=</B> <I>operand</I> 
        | <I>operand</I> <B>!=</B> <I>operand</I> 
        | <I>operand</I> <B>&lt;&gt;</B> <I>operand</I> 
        | <I>operand</I> <B>&lt;</B> <I>operand</I> 
        | <I>operand</I> <B>&lt;=</B> <I>operand</I> 
        | <I>operand</I> <B>&gt;</B> <I>operand</I> 
        | <I>operand</I> <B>&gt;=</B> <I>operand</I> 
        | <I>operand</I> (<B>not</B>) <B>like</B> <I>operand</I> 
        | <I>operand</I> (<B>not</B>) <B>like</B> <I>operand</I> <B>escape</B> <I>string</I>
        | <I>operand</I> (<B>not</B>) <B>match</B> <I>operand</I>
        | <I>operand</I> (<B>not</B>) <B>in</B> <I>operand</I>
        | <I>operand</I> (<B>not</B>) <B>in</B> <I>expressions-list</I>
        | <I>operand</I> (<B>not</B>) <B>between</B> <I>operand</I> <B>and</B> <I>operand</I>
	| <I>operand</I> <B>is</B> (<B>not</B>) <B>null</B>
<I>operand</I> ::= <I>addition</I>
<I>additions</I> ::= <I>multiplication</I> 
        | <I>addition</I> <B>+</B>  <I>multiplication</I>
        | <I>addition</I> <B>||</B> <I>multiplication</I>
        | <I>addition</I> <B>-</B>  <I>multiplication</I>
<I>multiplication</I> ::= <I>power</I> 
        | <I>multiplication</I> <B>*</B> <I>power</I>
        | <I>multiplication</I> <B>/</B> <I>power</I>
<I>power</I> ::= <I>term</I>
        | <I>term</I> <B>^</B> <I>power</I>
<I>term</I> ::= <I>identifier</I> | <I>number</I> | <I>string</I> 
        | <B>true</B> | <B>false</B> | <B>null</B> 
	| <B>current</B> | <B>first</B> | <B>last</B>
	| <B>(</B> expression <B>)</B> 
        | <B>not</B> <I>comparison</I>
	| <B>-</B> term
	| <I>term</I> <B>[</B> expression <B>]</B> 
	| <I>identifier</I> <B>.</B> <I>term</I> 
	| <I>function</I> <I>term</I>
        | <B>exists</B> <I>identifier</I> <B>:</B> <I>term</I>
<I>function</I> ::= <B>abs</B> | <B>length</B> | <B>lower</B> | <B>upper</B>
        | <B>integer</B> | <B>real</B> | <B>string</B> | <I>user-function</I>
<I>string</I> ::= <B>'</B> { { <I>any-character-except-quote</I> } (<B>''</B>) } <B>'</B>
<I>expressions-list</I> ::= <B>(</B> <I>expression</I> { <B>,</B> <I>expression</I> } <B>)</B>
<I>order</I> ::= <B>order by</B> <I>sort-list</I>
<I>sort-list</I> ::= <I>field-order</I> { <B>,</B> <I>field-order</I> }
<I>field-order</I> ::= [<B>length</B>] <I>field</I> (<B>asc</B> | <B>desc</B>)
<I>field</I> ::= <I>identifier</I> { <B>.</B> <I>identifier</I> }
<I>traverse</I> ::= <B>start from</B> <I>field</I> ( <B>follow by</B> <I>fields-list</I> )
<I>fields-list</I> ::=  <I>field</I> { <B>,</B> <I>field</I> }
<I>user-function</I> ::= <I>identifier</I>
</PRE><P>

Identifiers are case sensitive, begin with a  a-z, A-Z, '_' or '$' 
character, contain only a-z, A-Z, 0-9, '_' or '$' characters, and
do not duplicate a SQL reserved word.<P>

<TABLE WIDTH=100%>
<CAPTION>List of reserved words</CAPTION>
<TR><TD>abs</TD><TD>and</TD><TD>asc</TD><TD>between</TD><TD>by</TD></TR>
<TR><TD>current</TD><TD>desc</TD><TD>escape</TD><TD>exists</TD><TD>false</TD></TR>
<TR><TD>first</TD><TD>follow</TD><TD>from</TD><TD>in</TD><TD>integer</TD></TR>
<TR><TD>is</TD><TD>length</TD><TD>like</TD><TD>last</TD><TD>lower</TD></TR>
<TR><TD>match</TD><TD>not</TD><TD>null</TD><TD>or</TD><TD>real</TD></TR>
<TR><TD>rectangle</TD><TD>start</TD><TD>string</TD><TD>true</TD><TD>upper</TD></TR>
</TABLE><P>

ANSI-standard comments may also be used. All characters after a double-hyphen up to
the end of the line are ignored.<P>

FastDB extends ANSI standard SQL operations by supporting bit manipulation 
operations. Operators <code>and</code>/<code>or</code> can be applied not only 
to boolean operands but also to operands of integer type. The result of applying the
<code>and</code>/<code>or</code> operator to integer operands is an integer
value with bits set by the bit-AND/bit-OR operation. Bit operations can be used
for efficient implementation of small sets. Also the rasing to a power
operation (x<B>^</B>y) is supported by FastDB for integer and floating point
types.<P> 


<H3><A NAME = "structure">Structures</A></H3>

FastDB accepts structures as components of records. Fields of the structure
can be accessed using the standard dot notation: <code>company.address.city</code>
<P>

Structure fields can be indexed and used in an <code>order by</code> 
specification. Structures can contain other structures as their components;
there are no limitations on the nesting level.<P>

The programmer can define methods for structures, which can be used
in queries with the same syntax as normal structure components. 
Such a method should have no arguments except a pointer to the object to which
it belongs (the <code>this</code> pointer in C++), and should return
an atomic value (of boolean, numeric, string or reference type).
Also the method should not change the object instance (immutable method).
If the method returns a string, this string should be allocated using the
<code>new char</code> operator, because it will be deleted after copying of 
its value.<P>

So user-defined methods can be used for 
the creation of <I>virtual</I> components - 
components which are not stored in the database, 
but instead are calculated
using values of other components. 
For example, the FastDB <code>dbDateTime</code>
type contains only integer timestamp components and such methods
as <code>dbDateTime::year()</code>, <code>dbDateTime::month()</code>...
So it is possible to specify queries like: "<code>delivery.year = 1999</code>"
in an application, where the <code>delivery</code> record field has 
<code>dbDateTime</code> type. Methods are executed in the context of the
application, where they are defined, and are not available to other 
applications and interactive SQL.<P>

<H3><A NAME = "array">Arrays</A></H3>
FastDB accepts arrays with dynamic length as components of records. 
Multidimensional arrays are not supported, but it is possible to
define an array of arrays. It is possible to sort records in the result set
by length of array field.
FastDB provides a set of special constructions for dealing with arrays:<P>

<OL>
<LI>It is possible to get the number of elements in the array by 
the <code>length()</code> function. 

<LI>Array elements can be fetched by the<code>[]</code> operator.
If an index expression is out of array range, an exception will be raised.

<LI>The operator <code>in</code> can be used to check if an array contains
a value specified by the left operand. This operation can be used only for arrays of
atomic type: with boolean, numeric, reference or string components.

<LI>Array can be updated using <code>update</code> method which creates copy of the array and returns
non-constant reference.

<LI>Iteration through array elements is performed by the <code>exists</code> 
operator. A variable specified after the <code>exists</code> keyword can be used
as an index in arrays in the expression preceeded by the <code>exists</code>
quantor. This index variable will iterate through all possible array
index values, until the value of the expression will become <code>true</code> or
the index runs out of range. The condition

<PRE>
        exists i: (contract[i].company.location = 'US')
</PRE>

will select all details which are shipped by companies 
located in 'US', while the query

<PRE>
        not exists i: (contract[i].company.location = 'US')
</PRE>

will select all details which are shipped from companies outside 'US'.<P>

Nested <code>exists</code> clauses are allowed. Using nested 
<code>exists</code>
quantors is equivalent to nested loops using the correspondent
index variables. For example the query

<PRE>
        exists column: (exists row: (matrix[column][row] = 0))
</PRE>

will select all records, containing 0 in elements of a <code>matrix</code> 
field, which has type array of array of integer.
This construction is equivalent to the following
two nested loops:

<PRE>
       bool result = false;
       for (int column = 0; column < matrix.length(); column++) { 
            for (int row = 0; row < matrix[column].length(); row++) { 
	         if (matrix[column][row] == 0) { 
                     result = true;
		     break;
                 }
            }
       }
</PRE>

The order of using indices is essential! 
The result of the following query execution
<PRE>
        <code>exists row: (exists column: (matrix[column][row] = 0))</code>
</PRE>

will be completely different from the result of the previous query.
In the last case, the program simply hangs due to an infinite loop
in case of empty matrices. 
</OL>


<H3><A NAME = "string">Strings</A></H3>

All strings in FastDB have varying length and the programmer should not
worry about specification of maximal length for character fields. 
All operations acceptable for arrays are also applicable to strings. 
In addition to them, strings have a set of own operations.
First of all, strings can be compared with each other using standard
relation operators. At present, FastDB supports only the
ASCII character set (corresponds to type <code>char</code> in C) and
byte-by-byte comparison of strings ignoring locality settings.<P>

The operator <code>like</code> can be used for 
matching a string with a pattern containing special wildcard characters
'%' and '_'. The character '_' matches any single character, 
while the character '%' matches zero or more characters.
An extended form of the <code>like</code> operator together with
the <code>escape</code> keyword can be used to handle the
characters '%' and '_' in the pattern as normal characters if 
they are preceded by a special escape character, specified after
the <code>escape</code> keyword.<P> 

If you rebuild GigaBASE with USE_REGEX macro, then you can use 
<code>match</code> operator implementing standard regular expressions
(based on GNU regex library). Second operand of this operator specified 
regular expression to be matched and should be string literal.<P>

It is possible to search substrings within a string by the <code>in</code>
operator. The expression <code>('blue' in color)</code> will be true
for all records which <code>color</code> field contains 'blue'. 
If the length of the searched string is greater than some threshold value 
(currently 512), a Boyer-Moore substring search algorithm is used instead 
of a straightforward search implementation.<P>

Strings can be concatenated by <code>+</code> or <code>||</code> operators.
The last one was added for compatibility with the ANSI SQL standard.
As far as FastDB doesn't support the implicit conversion to string type in 
expressions, the semantic of the operator <code>+</code> can be redefined for
strings.<P>


<H3><A NAME = "reference">References</A></H3>

References can be dereferenced using the same dot notation as used for
accessing structure components. For example the following query

<PRE>
        company.address.city = 'Chicago'
</PRE>

will access records referenced by the <code>company</code> component of
a <code>Contract</code> record and extract the city component of the
<code>address</code> field of the referenced record from 
the <code>Supplier</code> table.<P>

References can be checked for <code>null</code> by <code>is null</code>
or <code>is not null</code> predicates. Also references can be compared for 
equality with each other as well as with the special <code>null</code>
keyword. When a null reference is dereferenced, an exception is raised
by FastDB.<P>

There is a special keyword <code>current</code>, which
during a table search can be used to refer to the current record.
Usually , the <code>current</code>
keyword is used for comparison of the current record identifier with
other references or locating it within an array of references. 
For example, the following query will search in the <code>Contract</code> 
table for all active contracts
(assuming that the field <code>canceledContracts</code> has a
<code>dbArray&lt; dbReference&lt;Contract&gt; &gt;</code> type): 

<PRE>
        current not in supplier.canceledContracts
</PRE><P>

FastDB provides special operators for recursive traverse of records by 
references:

<PRE>
     <code>start from</code> <I>root-references</I>
     ( <code>follow by</code> <I>list-of-reference-fields</I> )
</PRE>

The first part of this construction is used to specify root objects. 
The nonterminal <I>root-references</I> should be a variable of reference or
of array of reference type. The two special keywords <code>first</code> and
<code>last</code> can be used here, locating the first/last record in the table
correspondingly. 
If you want to check all records
referenced by an array of references or a single reference field
 for some condition, then this
construction can be used without the <code>follow by</code> part.<P>

If you specify the follow by part, then FastDB will recursively traverse 
the table of records, starting from the root
references and using a 
<I>list-of-reference-fields</I> for transition between records.
The <I>list-of-reference-fields</I> should consist of fields of
reference or of array of reference type. The traverse is done in depth first
top-left-right order (first we visit the parent node and then the siblings in 
left-to-right order).
The recursion terminates when a null reference is accessed
or an already visited record is referenced. For example the following
query will search a tree of  records with weight larger than 1 in TLR order:<P>

<PRE>
        "weight > 1 start from first follow by left, right"
</PRE><P>

For the following tree:

<PRE>
                              A:1.1
              B:2.0                             C:1.5
      D:1.3         E:1.8                F:1.2         G:0.8
</PRE>

the result of the query execution will be: 

<PRE>
('A', 1.1), ('B', 2.0), ('D', 1.3), ('E', 1.8), ('C', 1.5), ('F', 1.2)
</PRE><P>



As was already mentioned FastDB always manipulates with objects and doesn't accept joins. 
Joins can be implemented using references. Consider the classical 
<code>Supplier-Shipment-Detail</code> examples:
 
<PRE>
struct Detail { 
    char const* name;
    double      weight;
    
    TYPE_DESCRIPTOR((KEY(name, INDEXED), FIELD(weight)));
};

struct Supplier { 
    char const* company;
    char const* address;

    TYPE_DESCRIPTOR((KEY(company, INDEXED), FIELD(address)));
};

struct Shipment { 
    dbReference&lt;Detail&gt;   detail;
    dbReference&lt;Supplier&gt; supplier;
    int4                  price;
    int4                  quantity;
    dbDateTime            delivery;

    TYPE_DESCRIPTOR((KEY(detail, HASHED), KEY(supplier, HASHED), 
		     FIELD(price), FIELD(quantity), FIELD(delivery)));
};
</PRE>

We want to get information about delivery of some concrete details from some concrete
suppliers. In relational database this query will be written something like this:

<PRE>
     select from Supplier,Shipment,Detail where 
                 Supplier.SID = Shipment.SID and Shipment.DID = Detail.DID 
		 and Supplier.company like ? and Supplier.address like ?
		 and Detail.name like ? 
</PRE>

In FastDB this request should be written as: 

<PRE>
     dbQuery q = "detail.name like",name,"and supplier.company like",company,
	         "and supplier.address like",address,"order by price";
</PRE>
     
FastDB will first perform index search in the table <code>Detail</code> for details
matching the search condition. Then it performs another index search to locate shipment 
records referencing selected details. Then sequential search is used to check the rest of
select predicate.
<P>

<H3><A NAME = "rectangle">Rectangle</A></H3>

GigaBASE has builtin support of spatial data. It provides <code>rectangle</code> type.
By default it has dimension 2 and integer coordinate types. It is possible to easily change
dimension or use floating point coordinates, but recompilation of GigaBASE is needed in 
this case.<P>

It is possible to use this type not only in geographical system for 
representing spatial objects but also in many other cases when date is organized as hyper-cube and queries specify range of values for each dimension, for example:

<PRE>
      select * from CAR where price between 20000 and 30000 
                          and producedYear between 1997 and 1999 
                          and mileage between 50000 and 100000;
</PRE>

If <code>%lt;price, producedYear, milage&gt;</code> are dimensions of the rectangle, 
then this query can be executed using only one indexed search in R-Tree.<P>

Rectangle fields can be indexed - <B>R-Tree</B> index is used in this case
The R-tree provides fast access to spatial data. Basically the idea behind
the R-Tree and the B-Tree are the same:
use a hierarchical structure with a high branching factor to reduce the
number of disk accesses. The R-tree is the extension of the B_tree for a
multidimensional object. A geometric object is represented by its minimum 
bounding rectangle (MBR). Non-leaf nodes contain entries of the form 
(R,<I>ptr</I>) where <I>ptr</I> is a pointer to a child node in the R-tree; R 
is the MBR that covers all rectangles in the child node. Leaf nodes contain 
entries of the form (obj-id, R) where
obj-id is a pointer to the object, and R is the MBR of the object. The main 
innovation in the R-tree is that the father nodes are allowed to overlap. By
this means the R-tree guarantees at least 50% space utilization and remains 
balanced. 
The first R-tree implementation was proposed by Guttman. The Gigabase <B>R-Tree</B>
class is based on Guttman's implementation with a quadratic split algorithm.
The quadratic split algorithm is the one that achieves the best trade-off
between splitting time and search performance.<P>

Rectangle class provides method for calculating distance between two rectangle, 
rectangle area, checking whether two rectangle overlap or one contains another.
Rectangle is specified by coordinates of two it's vertices. Rectangle class
contains array of coordinates. Coordinates of first vertex are placed at the 
beginning of array, and then - coordinates of another vertex.
Each coordinate of first vertex should not be large than correspondent coordinate of 
the second vertex. Singular rectangle with one or more coordinates of first vertex equals 
to the correspondent coordinate of the second vertex are allowed - this is a way of storing
points in the database.<P>

SubSQL provides some special operators for dealing with rectangle. First of all - 
all comparison operators can be used with the following semantic:<P>

<TABLE BORDER ALIGN=CENTER>
<TR><TD><code>a == b</code></TD><TD>Rectangle <code>a</code> is the same as rectangle <code>b</code></TD></TR>
<TR><TD><code>a != b</code></TD><TD>Rectangle <code>a</code> is not the same as rectangle <code>b</code></TD></TR>
<TR><TD><code>a &lt;= b</code></TD><TD>Rectangle <code>b</code> contains rectangle <code>a</code></TD></TR>
<TR><TD><code>a &lt; b</code></TD><TD>Rectangle <code>b</code> contains rectangle <code>a</code> and them are not the same</TD></TR>
<TR><TD><code>a &gt;= b</code></TD><TD>Rectangle <code>a</code> contains rectangle <code>b</code> and are not the same</TD></TR>
<TR><TD><code>a &gt; b</code></TD><TD>Rectangle <code>b</code> contains rectangle <code>a</code> and them are not the same</TD></TR>
</TABLE><P>

Also SubSQL provides <code>overlaps</code> and <code>in</code> operators.
First checks if two rectangles overlap, the second is equivalent to <code>&lt;=</code> operator.
Rectangles can be added - result is minimal rectangle containing both rectangles-operands.
It is possible to access rectangle as array of coordinates - using <code>[index]</code>
notation. Coordinates in query are always returned as real numbers.<P>

Optimizer is able to use spatial index for all comparison operators (except <code>!=</code>)
and for <code>overlaps</code> operator.<P>


<H3><A NAME = "function">Functions</A></H3>
<TABLE BORDER ALIGN="center">
<CAPTION>Predefined functions</CAPTION>
<TR><TH>Name</TH><TH>Argument type</TH><TH>Return type</TH><TH>Description</TH></TR>
<TR><TD>abs</TD><TD>integer</TD><TD>integer</TD><TD>absolute value of the argument</TD</TR>
<TR><TD>abs</TD><TD>real</TD><TD>real</TD><TD>absolute value of the argument</TD</TR>
<TR><TD>area</TD><TD>rectangle</TD><TD>real</TD><TD>area of the rectangle</TD></TR>
<TR><TD>integer</TD><TD>real</TD><TD>integer</TD><TD>conversion of real to integer</TD</TR>
<TR><TD>length</TD><TD>array</TD><TD>integer</TD><TD>number of elements in array</TD</TR>
<TR><TD>lower</TD><TD>string</TD><TD>string</TD><TD>lowercase string</TD</TR><TR><TD>real</TD><TD>integer</TD><TD>real</TD><TD>conversion of integer to real</TD</TR>
<TR><TD>string</TD><TD>integer</TD><TD>string</TD><TD>conversion of integer to string</TD</TR>
<TR><TD>string</TD><TD>real</TD><TD>string</TD><TD>conversion of real to string</TD</TR>
<TR><TD>upper</TD><TD>string</TD><TD>string</TD><TD>uppercase string</TD</TR>
</TABLE><P>

FastDB allows user to define its own functions and operators.
Function should have at least one but no more than 3 parameters of string, integer, 
boolean, reference or user defined (raw binary) type. It should return value of integer, real, string or
boolean type.<P>
User functions should be registered by the <code>USER_FUNC(f)</code> macro, 
which creates a static object of the <code>dbUserFunction</code> class, binding 
the function pointer and the function name.<P>
There are two ways of implementing these functions in application.
First can be used only for functions with one argument. This argument should be of <code>int8, real8,
char*</code> types. And the function return type should be <code>int8, real8, char*</code> or <code>bool</code>.
If function has more than one parameters or it can accept parameters of different types (polymorphism)
then parameters should be passed as reference to <code>dbUserFunctionArgument</code> structure.
This structure contains <code>type</code> field, which value can be used in function implementation to
detect type of passed argument and union with argument value.
The following table contains mapping between argument types and where the value should be taken from:<P>

<TABLE BORDER ALIGN=CENTER>
<TR><TH>Argument type</TH><TH>Argument value</TH><TH>Argument value type</TH></TR>
<TR><TD><code>dbUserFunctionArgument::atInteger</code></TD><TD><code>u.intValue</code></TD><TD><code>int8</code></TD></TR>
<TR><TD><code>dbUserFunctionArgument::atBoolean</code></TD><TD><code>u.boolValue</code></TD><TD><code>bool</code></TD></TR>
<TR><TD><code>dbUserFunctionArgument::atString</code></TD><TD><code>u.strValue</code></TD><TD><code>char const*</code></TD></TR>
<TR><TD><code>dbUserFunctionArgument::atReal</code></TD><TD><code>u.realValue</code></TD><TD><code>real8</code></TD></TR>
<TR><TD><code>dbUserFunctionArgument::atReference</code></TD><TD><code>u.oidValue</code></TD><TD><code>oid_t</code></TD></TR>
<TR><TD><code>dbUserFunctionArgument::atRawBinary</code></TD><TD><code>u.rawValue</code></TD><TD><code>void*</code></TD></TR>
</TABLE><P>


For example the following
statements make it possible to use the <code>sin</code> function in SQL
statements:

<PRE>
        #include &lt;math.h&gt;
	...
        USER_FUNC(sin);
</PRE>


Functions can be used only
within the application, where they are defined. Functions are not accessible
from other applications and interactive SQL. If a function returns a string
type , the returned string should be copied by means of the operator
<code>new</code>, because
FastDB will call the destructor after copying the returned value.<P>

In FastDB, the function argument can (but not necessarily must) be enclosed in 
parentheses. So both of the following expressions are valid:

<PRE>
        '$' + string(abs(x))
	length string y
</PRE><P>

Functions with two argument can be also used as operators. Consider the following example, 
in which function <code>contains</code> which performs case insensitive search for substring is defined:

<PRE>
     bool contains(dbUserFunctionArgument& arg1, dbUserFunctionArgument& arg2) { 
         assert(arg1.type == dbUserFunctionArgument::atString 
	     && arg2.type == dbUserFunctionArgument::atString);
         return stristr(arg1.u.strValue, arg2.u.strValue) != NULL;
     }

     USER_FUNC(contains);
    
     dbQuery q1, q2;
     q1 = "select * from TestTable where name contains 'xyz'";
     q2 = "select * from TestTable where contains(name, 'xyz')";
</PRE>

In this example, queries <code>q1</code> and <code>q2</code> are equivalent.<P>



<H2><A NAME = "cpp">C++ interface</A></H2>
One of the primary goals of FastDB is to provide a flexible and convenient
application language interface. Anyone who has  to use 
ODBC or similar SQL interfaces will understand what I am speaking about.
In FastDB, a query can be written in C++ in the following way:<P>

<PRE>
    dbQuery q; 
    dbCursor&lt;Contract&gt; contracts;
    dbCursor&lt;Supplier&gt; suppliers;
    int price, quantity;
    q = "(price >=",price,"or quantity >=",quantity,
        ") and delivery.year=1999";
    // input price and quantity values
    if (contracts.select(q) != 0) { 
        do { 
            printf("%s\n", suppliers.at(contracts->supplier)->company);
        } while (contracts.next());
    } 
</PRE>

<H3><A NAME = "table">Table</A></H3>

Data in FastDB is stored in tables which correspond to C++ classes
whereas the table records correspond to class instances. 
The following C++ types are accepted as atomic components of
FastDB records:<P>

<TABLE BORDER ALIGN="center">
<TR><TH>Type</TH><TH>Description</TH></TR>
<TR><TD>bool</TD><TD>boolean type (<code>true,false</code>)</TD></TR>
<TR><TD>int1</TD><TD>one byte signed integer (-128..127)</TD></TR>
<TR><TD>int2</TD><TD>two bytes signed integer (-32768..32767)</TD></TR>
<TR><TD>int4</TD><TD>four bytes signed integer (-2147483648..2147483647)</TD></TR>
<TR><TD>int8</TD><TD>eight bytes signed integer (-2**63..2**63-1)</TD></TR>
<TR><TD>real4</TD><TD>four bytes ANSI floating point type</TD></TR>
<TR><TD>real8</TD><TD>eight bytes ANSI double precision floating point type</TD></TR>
<TR><TD>char const*</TD><TD>zero terminated string</TD></TR>
<TR><TD>dbReference&lt;T&gt;</TD><TD>reference to class T</TD></TR>
<TR><TD>dbArray&lt;T&gt;</TD><TD>dynamic array of elements of type T</TD></TR>
</TABLE><P>

In addition to types specified in the table above, FastDB records can
also contain nested structures of these components. 
FastDB doesn't support unsigned types to simplify the query language,
to  eliminate bugs caused by signed/unsigned comparison
and to reduce the size of the database engine.<P>

Unfortunately C++ provides no way
to get metainformation about a class at runtime (RTTI is not supported by all 
compilers and also doesn't provide enough information).
Therefore the programmer 
has to explicitly enumerate class fields to be included in the database table 
(it also makes mapping between classes and tables more flexible). 
FastDB provides a set of macros and classes to make such mapping as simple as 
possible.<P>

Each C++ class or structure, which will be used in the database, should 
contain a special method describing its fields. The macro 
<code>TYPE_DESCRIPTOR(</code><I>field_list</I><code>)</code> will construct 
this method. The single argument of this macro is - enclosed in parentheses -
a list of class field descriptors.
If you want to define some methods for the class
and make them available for the database, then the macro 
<code>CLASS_DESCRIPTOR(</code><I>name, field_list</I><code>)</code>
should be used instead of <code>TYPE_DESCRIPTOR</code>. The class name is
needed to get references to member functions.<P>

The following macros can be used for the construction of field
descriptors:

<DL>
<DT><B>FIELD(</B>name<B>)</B><DD>Non-indexed field with specified name.
<DT><B>KEY(</B>name, index_type<B>)</B><DD>Indexed field. <I>index_type</I> 
should be a combination of <code>HASHED</code> and <code>INDEXED</code> flags.
When the <code>HASHED</code> flag is specified, FastDB will create a hash table
for the table using this field as a key. When the <code>INDEXED</code> flag is 
specified, FastDB will create a (special kind of index) T-tree for the table 
using this field as a key. 
<DT><B>UDT(</B>name, index_type, comparator<B>)</B><DD>User defined raw binary type. 
Database deals with this type just as with sequence of bytes of specified size.
This field can be used in query (compared with query parameter of the same type), 
may be indexed and used in <code>order by</code> clause. Comparison is performed by means of
<code>comparator</code> function provided by programmer. Comparator functions receives three
arguments: two pointers to the compared raw binary objects and size of binary object.
The semantic of <I>index_type</I> is the same as of <code>KEY</code> macro.
<DT><B>RAWKEY(</B>name, index<B>)</B><DD>Raw binary type with predefined comparator.
This macro is just specialized version of <code>UDT</code> macro with <code>memcmp</code>
used as comparator.
<DT><B>RAWFIELD(</B>name<B>)</B><DD>One more specialization of <code>UDT</code> macro
for raw binary fields with predefined comparator <code>memcmp</code> and without indices.
<DT><B>SUPERCLASS(</B>name<B>)</B><DD>Specifies information about the base class
(parent) of the current class.
<DT><B>RELATION(</B>reference, inverse_reference<B>)</B>
<DD>Specifies <I>one-to-one, one-to-many</I> or <I>many-to-many</I>
relationships between classes (tables). Both <I>reference</I>
and <I>inverse_reference</I>
fields should be of reference or of array of reference type.
<code>inverse_reference</code> is a field of the referenced table
containing the inverse reference(s) to the current table. Inverse references
are automatically updated by FastDB and are used for query optimization
(see <A HREF="#inverse">Inverse references</A>).
<DT><B>OWNER(</B>reference, inverse_reference<B>)</B>
<DD>Specifies <I>one-to-many</I> or <I>many-to-many</I>
relationship between classes (tables) of owner-member type. 
When owner record is removed all referenced member records are also removed
(cascade delete). If member record has reference to owner class, it should be 
declared with RELATION macro.
<DT><B>METHOD(</B>name<B>)</B><DD>Specifies a method of the class.
The method should be a parameterless instance member function
returning a
boolean, numeric, reference or string type. Methods should be specified after 
all other attributes of the class. 
</DL><P>

Although only atomic fields can be indexed, an index type can be specified 
for structures. The index will be created for components of the structure
only if such type of index is specified in the index type mask of the 
structure. This allows the programmers to enable or disable indices for 
structure fields depending on the role of the structure in the record.<P>

The following example illustrates the creation of a type descriptor 
in the header file:<P>

<PRE>
class dbDateTime { 
    int4 stamp;
  public:
 
    int year() { 
	return localtime((time_t*)&stamp)-&gt;tm_year + 1900;
    }
    ...

    CLASS_DESCRIPTOR(dbDateTime, 
		     (KEY(stamp,INDEXED|HASHED), 
		      METHOD(year), METHOD(month), METHOD(day),
		      METHOD(dayOfYear), METHOD(dayOfWeek),
		      METHOD(hour), METHOD(minute), METHOD(second)));
};    

class Detail { 
  public:
    char const* name;
    char const* material;
    char const* color;
    real4       weight;

    dbArray&lt; dbReference&lt;Contract&gt; &gt; contracts;

    TYPE_DESCRIPTOR((KEY(name, INDEXED|HASHED), 
		     KEY(material, HASHED), 
		     KEY(color, HASHED),
		     KEY(weight, INDEXED),
		     RELATION(contracts, detail)));
};

class Contract { 
  public:
    dbDateTime            delivery;
    int4                  quantity;
    int8                  price;
    dbReference&lt;Detail&gt;   detail;
    dbReference&lt;Supplier&gt; supplier;

    TYPE_DESCRIPTOR((KEY(delivery, HASHED|INDEXED), 
		     KEY(quantity, INDEXED), 
		     KEY(price, INDEXED),
		     RELATION(detail, contracts),
		     RELATION(supplier, contracts)));
};
</PRE>

Type descriptors should be defined for all classes used in the database.
In addition to defining type descriptors, it is necessary to establish
a mapping between C++ classes and database tables. The macro 
<code>REGISTER(</code>name<code>)</code> will do it. Unlike the
<code>TYPE_DESCRIPTOR</code> macro, the <code>REGISTER</code> macro should
be used in the implementation file and not in the header file. It constructs
a descriptor of the table associated with the class. If you are going to work
with multiple databases from one application, it is possible to register
a table in a concrete database by means of the
<code>REGISTER_IN(</code>name,database</code<code>)</code> macro. 
The parameter <code>database</code> of this macro should be a pointer to the
<code>dbDatabase</code> object. You can register tables
in the database as follows:<P>

<PRE>
REGISTER(Detail);
REGISTER(Supplier);
REGISTER(Contract);
</PRE>

The table (and correspondent class) can be used only with one database 
at each moment of time. When you open a database, FastDB imports into
the database all classes defined in the application.
If a class with the same name already exists 
in the database, its descriptor stored in the database is compared with the
descriptor of this class in the application. If the class definitions
differ, FastDB tries to convert records from the table to the new 
format. Any kind of conversion between numeric types (integer to
real, real to integer, with extension or truncation) is allowed. Also,
addition of new fields can be easily handled. But removal of fields
is only possible for empty tables (to avoid accidental data destruction).<P>

After loading all class descriptors, FastDB checks if all indices specified 
in the application class descriptor are already present in the database, 
constructs new indices and
removes indices, which are no more used. Reformatting the table and 
adding/removing indices is only possible when no more than one
application accesses the database. So when the first application is attached
to the database, it can perform table conversion. All other applications
can only add new classes to the database.<P>

There is one special internal database  <code>Metatable</code>, which
contains information about other tables in the database. C++ programmers
need not access this table, because the format of database tables is specified
by C++ classes. But in an interactive SQL program, it may be necessary to
examine this table to get information about record fields.<P>

Starting from version 2.30 FastDB supports autoincrement fields
(fields unique value to which are assigned automaticaly by database).
To be able to use them you should:<P>

<OL>
<LI>Recompile FastDB and your application with <code>-DAUTOINCREMENT_SUPPROT</code> flags 
(add this flag to <code>DEFS</code> variables in FastDB makefile).<BR>
<B>Attention</B>: database files created by FastDB compiled without this option will be incompatible 
with FastDB compiled with <code>DAUTOINCREMENT_SUPPORT</code>.

<LI>If you want to use other than 0 initial counter value, you should
asssign value to <code>dbTableDescriptor::initialAutoincrementCount</code>.
It will be shared between all tables, so all table will have the same initial value of 
autoincrement counter.

<LI>Autoincrement fields should be of int4 type and should be declared
with <code>AUTOINCREMENT</code> flag:

<PRE>
        class Record {
             int4 rid;
             char const* name;
             ...
       
             TYPE_DESCRIPTOR((KEY(rid, AUTOINCREMENT|INDEXED), FIELD(name), ...));
       }
</PRE>       
       
<LI>When record with autoincrement field is inserted in the database
there is no need to specify value of autoincremented field (it will be
ignored). After successful insertion of record this field will be
assigned unique value (which is guaranteed to be not used before this
table):

<PRE>
       Record rec;
       // no rec.rid should be specified
       rec.name = "John Smith";
       insert(rec);
       // rec.rid now assigned unique value
       int newRecordId  = rec.rid; // and can be used to reference this record
</PRE>

<LI>When record is removed the value will not be reused.
When transaction is aborted, table autoincrement counter is also rolled back.
</OL><P>


<H3><A NAME = "query">Query</A></H3>
The class query is used to serve two purposes: 

<OL>
<LI>to construct a query and bind query parameters
<LI>to cache compiled queries
</OL>

FastDB provides overloaded '<code>=</code>' and '<code>,</code>' C++ operators
to construct query statements with parameters. Parameters can be specified  
directly in places where they are used, eliminating any mapping between
parameter placeholders and C variables. In the following sample query,
pointers to the parameters <code>price</code> and <code>quantity</code> 
are stored in the query, so that the query can be executed several times
with different parameter values. C++ overloaded functions make it possible
to automatically determine the type of the parameter, 
requiring no extra information
to be supplied by the programmer (such reducing the possibility of a bug). 

<PRE>
        dbQuery q;
        int price, quantity;
        q = "price >=",price,"or quantity >=",quantity;
</PRE> 

Since the  <code>char*</code> type can be used both for specifying a fraction
of a query (such as "price >=") and for a parameter of string type,
FastDB uses a special rule to resolve this ambiguity. This rule is based on the
assumption that there is no reason for splitting a query text into two strings
like ("price ",">=") or specifying more than one parameter sequentially
("color=",color,color). So FastDB assumes the first string to be a fraction
of the query text and switches to <I>operand mode</I>
after it. In <I>operand mode</I>, FastDB treats the <code>char*</code> argument
as a query parameter and switches back to query <I>text mode</I>, and so on...
It is also possible not to use this "syntax sugar" and construct
query elements explicitly by the 
<code>dbQuery::append(dbQueryElement::ElementType type, void const* ptr)</code>
method. Before appending elements to the query,
it is necessary to reset the query by the <code>dbQuery::reset()</code> method
('<code>operator=</code>' does it automatically).<P>

It is not possible to use C++ numeric constants as query parameters, because
parameters are accessed by reference. But it is possible to use string
constants, because strings are passed by value. There two possible ways of 
specifying string parameters in a query: using a string buffer or a
pointer to pointer to string:<P>

<PRE>
     dbQuery q;
     char* type;
     char name[256];
     q = "name=",name,"and type=",&type;

     scanf("%s", name);
     type = "A";     
     cursor.select(q);
     ...
     scanf("%s", name);
     type = "B";     
     cursor.select(q);
     ...
</PRE><P>


Query variables can neither be passed to a function as a parameter
nor be assigned to another variable.
When FastDB compiles the query, it saves the compiled tree in this object. 
The next time the query will be used, 
no compilation is needed and the already compiled
tree can be used. It saves some time needed for query compilation.<P>

FastDB provides two approaches to integrate user-defined types in databases.
The first - the definition of class methods - was already mentioned. 
The other approach deals only with query construction. Programmers should
define methods, which will not do actual calculations, but instead
return an expression (in terms of predefined database types), which
performs the necessary calculation. It is better to describe it by example.
FastDB has no builtin datetime type. Instead of this, a normal C++
class <code>dbDateTime</code> can be used by the programmer. This class defines
methods allowing to specify datetime fields in ordered lists and
to compare two dates using normal relational operators:<P>

<PRE>
class dbDateTime { 
    int4 stamp;
  public:
    ...
    dbQueryExpression operator == (char const* field) { 
	dbQueryExpression expr;
	expr = dbComponent(field,"stamp"),"=",stamp;
	return expr;
    }
    dbQueryExpression operator != (char const* field) { 
	dbQueryExpression expr;
	expr = dbComponent(field,"stamp"),"<>",stamp;
	return expr;
    }
    dbQueryExpression operator &lt; (char const* field) { 
	dbQueryExpression expr;
	expr = dbComponent(field,"stamp"),">",stamp;
	return expr;
    }
    dbQueryExpression operator &lt;= (char const* field) { 
	dbQueryExpression expr;
	expr = dbComponent(field,"stamp"),">=",stamp;
	return expr;
    }
    dbQueryExpression operator &gt; (char const* field) { 
	dbQueryExpression expr;
	expr = dbComponent(field,"stamp"),"<",stamp;
	return expr;
    }
    dbQueryExpression operator &gt;= (char const* field) { 
	dbQueryExpression expr;
	expr = dbComponent(field,"stamp"),"<=",stamp;
	return expr;
    }
    friend dbQueryExpression between(char const* field, dbDateTime& from,
				     dbDateTime& till)
    { 
	dbQueryExpression expr;
	expr=dbComponent(field,"stamp"),"between",from.stamp,"and",till.stamp;
	return expr;
    }

    friend dbQueryExpression ascent(char const* field) { 
	dbQueryExpression expr;
	expr=dbComponent(field,"stamp");
	return expr;
    }	
    friend dbQueryExpression descent(char const* field) { 
	dbQueryExpression expr;
	expr=dbComponent(field,"stamp"),"desc";
	return expr;
    }	
};
</PRE>

All these methods receive as their parameter a name of a field in the record.
This name is used to contract the full name of the record's component.
This  can be done by class <code>dbComponent</code>, which constructor takes
the name of the structure field and the name of the component of the structure
and returns a compound name separated by a '.' symbol.
The class <code>dbQueryExpression</code> is used to collect expression items.
The expression is automatically enclosed in parentheses, eliminating conflicts
with operator precedence.<P>

So, assuming a record containing a field <code>delivery</code>
of dbDateTime type, it is possible
to construct queries like these:

<PRE>
        dbDateTime from, till;
        q1 = between("delivery", from, till),"order by",ascent("delivery");
        q2 = till &gt;= "delivery"; 
</PRE>

In addition to these methods, some class specific method can be defined
in such way, for example the method <code>overlaps</code> for a region type.
The benefit of this approach is that a database engine will work
with predefined types and is able to apply indices and other optimizations
to proceed such query. And from the other side, the encapsulation of the class
implementation is preserved, so programmers should not rewrite all queries
when a class representation is changed.<P>

Variables of the following C++ types can be used as query parameters:<P>

<TABLE BORDER ALIGN="center">
<TR><TD WIDTH=50%>int1</TD><TD WIDTH=50%>bool</TD></TR>
<TR><TD>int2</TD><TD>char const*</TD></TR>
<TR><TD>int4</TD><TD>char **</TD></TR>
<TR><TD>int8</TD><TD>char const**</TD></TR>
<TR><TD>real4</TD><TD>dbReference&lt;T&gt;</TD></TR>
<TR><TD>real8</TD><TD>dbArray&lt; dbReference&lt;T&gt; &gt;</TD></TR>
</TABLE><P>



<H3><A NAME = "cursor">Cursor</A></H3>
Cursors are used to access records returned by a select statement. 
FastDB provides typed cursors, i.e. cursors associated with concrete tables.
There are two kinds of cursors in FastDB: readonly cursors and cursors for 
update. Cursors in FastDB are represented by the  C++ template class 
<code>dbCursor&lt;T&gt;</code>, 
where <code>T</code> is the name of a C++ class associated with
the database table. The cursor type should be specified in the constructor
of the cursor. By default, a read-only cursor is created.
To create a cursor for update, you should pass a parameter 
<code>dbCursorForUpdate</code> to the constructor.<P>

A query is executed either by the cursor
<code>select(dbQuery& q)</code> method.
Or by the <code>select()</code> method, 
which can be used to iterate through
all records in the table. Both methods return the number of selected records
and set the current position to the first record (if available).
A cursor can be scrolled in forward or backward direction.
The methods <code>next(), prev(), first(), last()</code> can be used to 
change the current position of the cursor. 
If no operation can be performed as there are no (more) records
available, these methods return <code>NULL</code>
and the cursor position is not changed.<P>

A cursor for class T contains an instance of class T, used for fetching the
current record. That is why table classes should have a default constructor
(constructor without parameters), which has no side effects. 
FastDB optimizes fetching records from the database, copying only data from
fixed parts of the object. String bodies are not copied, instead
of this  the correspondent field points directly into the database. The same is
true for arrays: their components have the same representation in the
database as in the application (arrays of scalar types or arrays of nested 
structures of scalar components).<P>

An application should not change
elements of strings and arrays in a database directly.
When an array method needs to update an array body,
it creates an in-memory copy of the array and updates this 
copy. If the programmer wants to update a string field, she/he should assign
to the pointer a new value, 
but don't change the string directly in the database.
It is recommended to use the <code>char const*</code> type instead of the
<code>char*</code> type for string components, 
to enable the compiler to detect the illegal usage of strings.<P>

The cursor class provides the 
<code>get()</code> method for obtaining a pointer to 
the current record (stored inside the cursor). Also the overloaded 
'<code>operator-&gt;</code>'
can be used to access components of the current record.
If a cursor is opened for update,
the current record can be changed and stored in the database
by the <code>update()</code> method or can be removed.
If the current record is removed, the next record becomes the
current. If there is no next record, then the previous record
(if it exists)  becomes the current. The method <code>removeAll()</code>
removes all records in the table.
Whereas the method <code>removeAllSelected</code> only removes 
all records selected by the cursor.<P>

When records are updated, the size of the database may increase.
Thus an extension of the database section in the virtual memory 
is needed. As a result of such remapping, base addresses of the section can be
changed and all pointers to database fields kept by applications will become 
invalid. FastDB automatically updates current records in all opened 
cursors when a database section is remapped. So, when a database is updated, 
the programmer should access record fields only through the cursor 
<code>-&gt;</code> method. She/he should  not use pointer variables.<P>

Memory used for the current selection can be released by the
<code>reset()</code> method.
This method is automatically called by the <code>select(), 
dbDatabase::commit(), dbDatabase::rollback()</code> methods
and the cursor destructor, so in most cases there is no need to
call the <code>reset()</code> method explicitly.<P>

Cursors can also be used to access records by reference. The method
<code>at(dbReference&lt;T&gt; const& ref)</code> sets the cursor to the record
pointed to by the reference. In this case, the selection consists exactly of
one record and the <code>next(), prev()</code> methods will always return 
<code>NULL</code>. Since cursors and references in FastDB are strictly 
typed, all necessary checking can be done statically by the compiler and 
no dynamic type checking is needed. The only kind of checking,
which is done at runtime, is checking for null references.
The object identifier of the current record in the cursor can be obtained by
the <code>currentId()</code> method.<P> 

It is possible to restrict the number of records returned by a select statement.
The cursor class has the two methods
<code>setSelectionLimit(size_t lim)</code> and
<code>unsetSelectionLimit()</code>,
which can be used to set/unset the limit
of numbers of records returned by the query. In some situations,
a  programmer may want to receive
only one record or only few first records;  so the query execution
time and size of consumed memory can be reduced by limiting the size of 
selection. But if you specify an order for selected records, 
the query with the restriction to 
<I>k</I> records will not return the first <I>k</I> records
with the smallest value of the key. Instead of this, arbitrary <I>k</I>
records will be taken and then sorted.<P>

So all operations with database data can be performed by means of
cursors. The only exception is the insert operation, for which 
FastDB provides an overloaded insert function:

<PRE>
        template&lt;class T&gt;
        dbReference&lt;T&gt; insert(T const& record);
</PRE>

This function will insert a record at the end of the table and return
a reference of the created object.
The order of insertion is strictly specified in FastDB
and applications can use this assumption about the record order in the
table. For applications widely using references for navigation between
objects, it is necessary to have some <I>root</I> object, from which a
traversal by references can be made. A good candidate for such root object
is the first record in the table (it is also the oldest record in the 
table). This record can be accessed by execution of the <code>select()</code>
method without parameter. The current record in the cursor will
be the first record in the table.<P>


The C++ API of FastDB defines a special <code>null</code> variable
of reference type.
It is possible to compare the <code>null</code> variable with references 
or assign it to the reference:<P>

<PRE>
        void update(dbReference&lt;Contract&gt; c) {
            if (c != null) { 
	        dbCursor&lt;Contract&gt; contract(dbCursorForUpdate);
		contract.at(c);
		contract-&gt;supplier = null;
            }
        }
</PRE>

<A NAME="relative-parameter-binding">
Query parameters usually are bound to C++ variables. In most cases in is convenient and 
flexible mechanism. But in multithreaded application, there is no warranty that the same 
query will not be executed at the same moment of time by another thread with different values
of parameters. One solution is to use synchronization primitives (critical sections or mutexes)
to prevent concurrent execution of the query. But this will lead to performance degradation.
FastDB is able to perform read requests in parallel, increasing total system throughput.
The other solution is to use delayed parameter binding. This approach is illustrated by the 
following example:<P>  

<PRE>
dbQuery q;

struct QueryParams { 
    int         salary;
    int         age;
    int         rank;
};

void open()
{
    QueryParams* params = (QueryParams*)NULL;
    q = "salary > ", params->salary, "and age < ", params->age, "and rank =", params->rank;
}

void find(int salary, int age, int rank) 
{ 
    QueryParams params;
    params.salary = salary;
    params.age = age;
    params.rank = rank;
    dbCursor&lt;Person&gt; cusor;
    if (cursor.select(q, &params) &gt; 0) { 
        do { 
	    cout &lt;&lt; cursor->name &lt;&lt; NL;
        } while (cursor.next());
    }
}
</PRE>

So in this example function <code>open</code> binds query parameters just to offsets of 
fields in structure. Later in <code>find</code> functions, actual pointer to the structure
with parameters is passed to the <code>select</code> structure. Function <code>find</code>
can be concurrently executed by several threads and only one compiled version of the query
is used by all these threads. This mechanism is available since version 2.25.<P>
</A>

<H3><A NAME = "database">Database</A></H3>
The class <code>dbDatabase</code> controls the application interactions
with the database. It performs synchronization of concurrent accesses to the
database, transaction management, memory allocation, error handling,...<P>

The constructor of <code>dbDatabase</code> objects allows programmers to specify
some database parameters:

<PRE>
    dbDatabase(dbAccessType type = dbAllAccess,
	       size_t dbInitSize = dbDefaultInitDatabaseSize,
	       size_t dbExtensionQuantum = dbDefaultExtensionQuantum,
	       size_t dbInitIndexSize = dbDefaultInitIndexSize,
	       int nThreads = 1);
</PRE>

The following database access type are supported:<P>

<TABLE BORDER>
<TR><TH>Access type</TH><TH>Description</TH></TR>
<TR><TD><code>dbDatabase::dbReadOnly</code></TD><TD>Read only mode</TD></TR>
<TR><TD><code>dbDatabase::dbAllAccess</code></TD><TD>Normal mode</TD></TR>
<TR><TD><code>dbDatabase::dbConcurrentRead</code></TD><TD>Read only mode in which application can access the database 
concurrently with application updating the same database in <code>dbConcurrentUpdate</code> mode</TD></TR>
<TR><TD><code>dbDatabase::dbConcurrentUpdate</code></TD><TD>Mode to be used in conjunction with
<code>dbConcurrentRead</code> to perform updates in the database without blocking read applications for a long time</TD></TR>
</TABLE><P>

When the database is opened in readonly  mode, no new class definitions can be added to the database and definitions
of existing classes and indices can not be altered.<P>

<code>dbConcurrentUpdate</code> and <code>dbConcurrentRead</code> modes should be used together when 
database is mostly accessed in readonly mode and updates should not block readers for a long time. 
In this mode update of the database can be performed concurrently with read accesses (readers will not see 
changed data until transaction is committed). Only at update transaction commit time, exclusive lock is set
but immediately released after incremental change of the current object index.<P>

So you can start one or more  applications using <code>dbConcurrentRead</code> mode and all their read-only
transactions will be executed concurrently. You can also start one or more applications using 
 <code>dbConcurrentUpdate</code> mode. All transactions of such applications will be synchronized using additional
global mutex. So all these transactions (even read-only) will be executed exclusively. But transactions of the application
running in <code>dbConcurrentUpdate</code> mode can run concurrently with transaction of applications
running in <code>dbConcurrentRead</code> mode! Please look at <code>testconc.cpp</code> example, 
illustrating usage of these modes<P>

<B>Attension!</B> Do not mix <code>dbConcurrentUpdate</code> and <code>dbConcurrentRead</code> 
mode with other modes and do not use them together in one process (so it is
not possible to start two threads in one of which open database in
dbConcurrentUpdate mode and in other - in dbConcurrentRead). Do not 
use <code>dbDatabase::precommit</code> method in <code>dbConcurrentUpdate</code> mode.<P>

The parameter <code>dbInitSize</code> specifies the initial size of the database file.
The database file increases on demand; setting the initial size can only 
reduce the number of reallocations (which can take a lot of time).
In the current implementation of the FastDB database
the size is at least doubled at each extension.
The default value of this parameter is 4 megabytes.<P>

The parameter <code>dbExtensionQuantum</code>
specifies the quantum of extension of the
memory allocation bitmap. 
Briefly speaking, the value of this parameter specifies how much memory
will be allocated sequentially without attempt to reuse space of
deallocated objects. The default value of this parameter is 4 Mb.
See section <A HREF="#memory">Memory allocation</A> for more details.<P> 

The parameter <code>dbInitIndexSize</code> specifies the initial index size. 
All objects in FastDB are accessed through an object index.
There are two copies of this object index:
current and committed. Object indices are reallocated on 
demand; setting an initial index size can only reduce (or increase)
the number of reallocations. The default value of this parameter is 64K object 
identifiers.<P>

And the last parameter <code>nThreads</code> controls the level of query
parallelization. If it is greater than 1, then FastDB can start the parallel
execution of some queries (including sorting the result). 
The specified number of parallel threads will
be spawned by the FastDB engine in this case. Usually it does not make
sense to specify the value of this parameter to be greater than the
number of online CPUs in the system. It is also possible to pass zero
as the value of this parameter. In this case, FastDB will automatically detect
the number of online CPUs in the system. The number of threads also can be set 
by the <code>dbDatabase::setConcurrency</code> method at any moment of time.<P>

The class <code>dbDatabase</code> contains a static field 
<code>dbParallelScanThreshold</code>, which specifies a threshold for the
number of records in the table after which query parallelization
is used. The default value of this parameter is 1000.<P>

The database can be opened by the
<code>open(char const* databaseName, char const* fileName = NULL, unsigned waitLockTimeout = INFINITE)</code> method.
If the file name parameter is omitted, it is constructed from
the database name by appending the ".fdb" suffix. The database name should
be an arbitrary identifier consisting of any symbols except '\'.
The last parameter <code>waitLockTimeout</code> can be set to prevent locking of all
active processes working with the database when some of them is crashed.
If the crashed process had locked the database, then no other process can continue 
execution. To prevent it, you can specify maximal delay for waiting for the lock, 
after expiration of which system will try to perform recovery and continue execution
of active processes.
The method&nbsp;<code>open</code> returns <code>true</code> if the database was
successfully opened; or <code>false</code> if the open operation failed. 
In the last case, the database <code>handleError</code> method is called with a
<code>DatabaseOpenError</code> error code. A database session can be terminated
by the <code>close</code> method, which implicitly commits current transactions.<P>

In a multithreaded application each thread, which wants to access the database,
should first be attached to it. The method <code>dbDatabase::attach()</code>
allocates thread specific data and attaches the thread to the database.
This method is automatically called by the <code>open()</code> method, so
there is no reason to call the <code>attach()</code> method for the thread,
which opens the database. When the thread finishes work with the database, it should
call the <code>dbDatabase::detach()</code> method. The method 
<code>close</code> automatically invokes the <code>detach()</code> method. 
The method <code>detach()</code> implicitly commits current transactions.
An attempt to access a database by a detached thread causes an assertion failure.<P>

FastDB is able to perform compilation and execution of queries in parallel, 
providing significant increase of performance in multiprocessor systems.
But concurrent updates of the database are not possible (this is the price
for the efficient log-less transaction mechanism and zero time recovery).
When an application wants to modify the database (open a cursor for update or
insert a new record in the table), it first locks the database in exclusive mode, 
prohibiting accesses to the database by other applications, even for
read-only queries. So to avoid blocking of database applications for a long 
time, the modification transaction should be as short as possible. 
No blocking operations (like waiting for input from the user) should be
done within this transaction.<P>

Using only shared and exclusive locks on the database
level, allows FastDB to almost eliminate overhead of locking and 
to optimize the speed of execution of non-conflicting operations. But if many 
applications simultaneously update different parts of the database, then the
approach used in FastDB will be very inefficient. That is why FastDB is most
suitable for a single-application database access model or for
multiple applications with a read-dominated access pattern model.<P>
 
Cursor objects should be used only by one thread in a
multithreaded application. If there are more than one threads in your
application, use local variables for cursors in each thread. 
It is possible to share query variables between threads, but take care about
query parameters. The query should either has no parameters, or 
<A HREF="#relative-parameter-binding">relative form</A> of parameters
binding should be used.<P>

The <code>dbDatabase</code> object is shared between all
threads and uses thread specific data to perform query
compilation and execution in parallel with minimal synchronization overhead.
There are few global things, which require synchronization: symbol table,
pool of tree node,... But scanning, parsing and execution of the query can
be done without any synchronization, providing high level of concurrency
at multiprocessor systems.<P>

A database transaction is started by the first select or an insert operation.
If a cursor for update is used, then the database is locked in exclusive
mode, prohibiting access to the database by other applications and threads.
If a read-only cursor is used, then the database is locked in shared mode, preventing 
other applications and threads from modifying the database,
but allowing the execution of concurrent read requests.
A transaction should be explicitly terminated
either by the <code>dbDatabase::commit()</code> method, which fixes all 
changes done by the transaction in the database; or by the
<code>dbDatabase::rollback()</code> method to undo all modifications 
done by transactions. The method <code>dbDatabase::close()</code> automatically 
commits current transactions.<P>

If you start a transaction by performing selection using a read-only cursor and
then use a cursor for update to perform some modifications of the database, 
the database will be first locked in shared mode; then the lock will be upgraded
to exclusive mode. This can cause a deadlock problem if the database is simultaneously 
accessed by several applications. Imagine that application A starts
a read transaction and application B also starts a read transaction. Both
of them hold shared locks on the database. If both of them want to
upgrade their locks to exclusive mode, they will forever block each other
(exclusive lock can not be granted until a shared lock of another process exists).
To avoid such situations try to use a cursor for update at the beginning of the
transaction; or explicitly use the <code>dbdatabase::lock()</code> method.
More information about the implementation of transactions in FastDB can be found 
in section <A HREF="#transaction">Transactions</A>.<P>

It is possible to explicitly lock the database by the <code>lock()</code> method. 
Locking is usually done automatically -  there are only few cases when
you will want to use this method. It will lock the database in exclusive
mode until the end of the current transaction.<P>

A backup of the database can be done by the 
<code>dbDatabase::backup(char const* file)</code>
method. A backup locks the database in shared mode and flushes an image of the
database from main memory to the specified file. Because of using a shadow object index, 
the database file is always in a consistent state, so recovery from the backup can
be performed just by renaming the backup file (if backup was performed on tape, it
should be first restored to the disk).<P>

The class <code>dbDatabase</code> is also responsible for handling various 
application errors, such as syntax errors during query compilation,
out of range index or null reference access during query execution.
There is a virtual method <code>dbDatabase::handleError</code>, which handles
these errors:


<PRE>
        virtual void handleError(dbErrorClass error, 
                                 char const*  msg = NULL, 
                                 int          arg = 0);
</PRE>

A programmer can derive her/his own subclass from the <code>dbDatabase</code>
class and redefine the default reaction on errors.<P>




<TABLE BORDER ALIGN="center">
<CAPTION>Error classes and default handling</CAPTION>
<TR><TH>Class</TH><TH>Description</TH><TH>Argument</TH><TH>Default reaction</TH></TR>
<TR><TD>QueryError</TD><TD>query compilation error</TD><TD>position in query string</TD><TD>abort compilation</TD></TR> 
<TR><TD>ArithmeticError</TD><TD>arithmetic error during division or power operations</TD><TD ALIGN="center">-</TD><TD>terminate application</TD></TR>
<TR><TD>IndexOutOfRangeError</TD><TD>index is out if array bounds</TD><TD>value of index</TD><TD>terminate application</TD></TR>
<TR><TD>DatabaseOpenError</TD><TD>error while database opening</TD><TD ALIGN="center">-</TD><TD>open method will return <code>false</code></TD></TR>
<TR><TD>FileError</TD><TD>failure of file IO operation</TD><TD>error code</TD><TD>terminate application</TD></TR>
<TR><TD>OutOfMemoryError</TD><TD>not enough memory for object allocation</TD><TD>requested allocation size</TD><TD>terminate application</TD></TR>
<TR><TD>Deadlock</TD><TD>upgrading lock causes deadlock</TD><TD ALIGN="center">-</TD><TD>terminate application</TD></TR>
<TR><TD>NullReferenceError</TD><TD>null reference is accessed during query execution<TD ALIGN="center">-</TD><TD>terminate application</TD></TR>
</TABLE><P>


<H2><A NAME = "cli">Call level interface</A></H2>

Interface described in previous section provides convenient and reliable mechanism for
accessing data from C++. It has two drawbacks:

<OL>
<LI>It is very C++ specific and can not be used with other programming languages
<LI>It is suitable only for local connections to the database (within one system).
</OL>

Interface described below outcomes these two restrictions. It consists of the set of
pure ANSI C functions and using it mapping of any programming language to the FastDB
database can be easily implemented. Connection between client and serves is performed by 
sockets (either local, either standard TCP/IP sockets). Certainly this interface is
less convenient and more error prone than C++ interface, but this is a cost of its 
flexibility. All types, constants and functions are declared in <A HREF="cli.h">cli.h</A>
file.<P>

FastDB provides multithreaded server for handling client CLI sessions. This server can be 
started from <A HREF="#subsql">SubSQL</A> utility by 
<code>start server 'HOST:PORT' &lt;number-of-threads&gt;</code> command. 
This server will accept local (within one system) and global clients connections and 
attach one thread from the threads pool to each connection. The size of thread's pool
is controlled by <i>number-of-threads</i> parameters. But the server can spawn more
than specified number of threads if there are many active connections. A thread is attached
to the client until the end of the session. If session is abnormally terminated, all
changes made by the client are rollbacked. The server can be stopped by correspondent
<code>stop server 'HOST:PORT'</code> command.<P>


<A NAME="cli_errors">
<TABLE><CAPTION><FONT SIZE=+1><B><U>CLI functions return codes</U></B></FONT></CAPTION>
<TR><TH>Error code</TH><TH>Description</TH></TR>
<TR><TD>cli_ok</TD><TD>Succeful completion</TD></TR>
<TR><TD>cli_bad_address</TD><TD>Invalid format of server URL</TD></TR>
<TR><TD>cli_connection_refused</TD><TD>Connection with server could not be established</TD></TR>
<TR><TD>cli_bad_statement</TD><TD>Text of SQL statement is not correct</TD></TR>
<TR><TD>cli_parameter_not_found</TD><TD>Parameter was not found in statement</TD></TR>
<TR><TD>cli_unbound_parameter</TD><TD>Parameter was not specified</TD></TR>
<TR><TD>cli_column_not_found</TD><TD>No sucj colunm in the table</TD></TR>
<TR><TD>cli_incompatible_type</TD><TD>Conversion between application and database type is not possible</TD></TR>
<TR><TD>cli_network_error</TD><TD>Connection with server is broken</TD></TR>
<TR><TD>cli_runtime_error</TD><TD>Error during query execution</TD></TR>
<TR><TD>cli_bad_descriptor</TD><TD>Invalid statement/session description</TD></TR>
<TR><TD>cli_unsupported_type</TD><TD>Unsupported type for parameter or colunm</TD></TR>
<TR><TD>cli_not_found</TD><TD>Record was not found</TD></TR>
<TR><TD>cli_not_update_mode</TD><TD>Attempt to update records selected by view only cursor</TD></TR> 
<TR><TD>cli_table_not_found</TD><TD>There is no table with specified name in the database</TD></TR>
<TR><TD>cli_not_all_columns_specified</TD><TD>Insert statement doesn't specify values for all table columns</TD></TR>
<TR><TD>cli_not_fetched</TD><TD><A HREF="#cli_fetch"><code>cli_fetch</code></A> method was not called</TD></TR>
<TR><TD>cli_already_updated</TD><TD><A HREF="#cli_update"><code>cli_update</code></A> method was invoked more than once for the same record</TD></TR>
<TR><TD>cli_table_already_exists</TD><TD>Attempt to create existed table</TD></TR>
<TR><TD>cli_not_implemented</TD><TD>Function is not implemented</TD></TR>
</TABLE></A>
    
<P>

<A NAME = "cli_types">
<TABLE><CAPTION><FONT SIZE=+1><B><U>Supported types</U></B></FONT></CAPTION>
<TR><TH>Type</TH><TH>Description</TH><TH>Size</TH></TR>
<TR><TD>cli_oid</TD><TD>Object identifier</TD><TD>4</TD></TR>
<TR><TD>cli_bool</TD><TD>Boolean type</TD><TD>1</TD></TR>
<TR><TD>cli_int1</TD><TD>Timy interger type</TD><TD>1</TD></TR>
<TR><TD>cli_int2</TD><TD>Small interger type</TD><TD>2</TD></TR>
<TR><TD>cli_int4</TD><TD>Interger type</TD><TD>4</TD></TR>
<TR><TD>cli_int8</TD><TD>Big interger type</TD><TD>8</TD></TR>
<TR><TD>cli_real4</TD><TD>Single precision floating point type</TD><TD>4</TD></TR>
<TR><TD>cli_real8</TD><TD>Double precision floating point type</TD><TD>8</TD></TR>
<TR><TD>cli_asciiz</TD><TD>Zero terminated string of bytes</TD><TD>1*N</TD></TR>
<TR><TD>cli_pasciiz</TD><TD>Pointer to zero terminated string</TD><TD>1*N</TD></TR>
<TR><TD>cli_array_of_oid</TD><TD>Array of references</TD><TD>4*N</TD></TR>
<TR><TD>cli_array_of_bool</TD><TD>Array of booleans</TD><TD>1*N</TD></TR>
<TR><TD>cli_array_of_int1</TD><TD>Array of tiny integers</TD><TD>1*N</TD></TR>
<TR><TD>cli_array_of_int2</TD><TD>Array of small integers</TD><TD>2*N</TD></TR>
<TR><TD>cli_array_of_int4</TD><TD>Array of integers</TD><TD>4*N</TD></TR>
<TR><TD>cli_array_of_int8</TD><TD>Array of big integers</TD><TD>8*N</TD></TR>
<TR><TD>cli_array_of_real4</TD><TD>Array of reals</TD><TD>4*N</TD></TR>
<TR><TD>cli_array_of_real8</TD><TD>Array of long reals</TD><TD>8*N</TD></TR>
<TR><TD>cli_any</TD><TD>can be used only for binding columns, server will use the same type for column as stored in the database</TD><TD>?</TD></TR>
<TR><TD>cli_datetime</TD><TD>time in seconds since 00:00:00 UTC, January 1, 1970.</TD><TD>4  </TD></TR>
<TR><TD>cli_autoincrement</TD><TD>column automatically assigned value during record insert</TD><TD>4</TD></TR>
<TR><TD>cli_rectangle</TD><TD>rectangle (by default R2 rectangle with int4 coordinates</TD><TD>dimension*2*sizeof(cli_coord_t)</TD></TABLE></A><P>

<HR> 

<A NAME = "cli_open"><pre>
int cli_open(char const* server_url, 
	     int         max_connect_attempts,
	     int         reconnect_timeout_sec);
</pre></A>
<DL><DD>
Establish connection with the server 
<DL>
<DT><B>Parameters</B>
<DD><code>server_url</code> - zero terminated string with server address and port, 
for example "localhost:5101", "195.239.208.240:6100",...
<DD><code>max_connect_attempts</code>  - number of attempts to establish connection
<DD><code>reconnect_timeout_sec</code> - timeput in seconds between connection attempts
<DT><B>Returns</B>
<DD><code>&gt;= 0</code> - connectiondescriptor to be used in all other cli calls
<DD><code>&lt;  0</code> - error code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<A NAME = "cli_close"><pre>
int cli_close(int session);
</pre></A>
<DL><DD>
Close session
<DL>
<DT><B>Parameters</B>
<DD><code>session</code> - session descriptor returned by <A HREF="#cli_open"><code>cli_open</code></A>
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<A NAME = "cli_statement"><pre>
int cli_statement(int session, char const* stmt);
</pre></A>
<DL><DD>
Specify SubSQL statement to be executed at server.
Binding to the parameters and columns can be established       
<DL>
<DT><B>Parameters</B>
<DD><code>session</code> - session descriptor returned by <A HREF="#cli_open"><code>cli_open</code></A>
<DD><code>stmt</code>    - zero terminated string with SubSQL statement  
<DT><B>Returns</B>
<DD><code>&gt;= 0</code> - statement descriptor
<DD><code>&lt;  0</code> - error code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<A NAME = "cli_parameter"><pre>
int cli_parameter(int         statement,
		  char const* param_name, 
		  int         var_type,
		  void*       var_ptr);
</pre></A>
<DL><DD>
Bind parameter to the statement
<DL>
<DT><B>Parameters</B>
<DD><code>statement</code>  - statememt descriptor returned by <A HREF="#cli_statement"><code>cli_statement</code></A>
<DD><code>param_name</code> - zero terminated string with parameter name.  
Paramter name should start with '%'
<DD><code>var_type</code>   - type of variable as described in cli_var_type enum.
Only scalar and zero terminated string types are supported.
<DD><code>var_ptr</code>  - pointer to the variable
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<A NAME = "cli_column"><pre>
int cli_column(int         statement,
	       char const* column_name, 
	       int         var_type, 
	       int*        var_len, 
	       void*       var_ptr);
</pre></A>
<DL><DD>
Bind extracted column of select or insert statement
<DL>
<DT><B>Parameters</B>
<DD><code>statement</code> - statememt descriptor returned by <A HREF="#cli_statement"><code>cli_statement</code></A>
<DD><code>column_name</code> - zero terminated string with column name  
<DD><code>var_type</code> - type of variable as described in cli_var_type enum
<DD><code>var_len</code> - pointer to the variable to hold length of array variable.
This variable should be assigned the maximal length of the array/string buffer, 
pointed by <code>var_ptr</code>. After the execution of the statement it is assigned the 
real length of the fetched array/string. If it is large than length of the buffer, 
then only part of the array will be placed in the buffer, but <code>var_len</code> 
still will contain the actual array length. 
<DD><code>var_ptr</code> - pointer to the variable
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<A NAME = "cli_array_column"><pre>
typedef void* (*cli_column_set)(int var_type, void* var_ptr, int len);
typedef void* (*cli_column_get)(int var_type, void* var_ptr, int* len);

int cli_array_column(int            statement,
		     char const*    column_name, 
		     int            var_type,
		     void*          var_ptr,
		     cli_column_set set,
		     cli_column_get get);
</pre></A>
<DL><DD>
Specify get/set functions for the array column
<DL>
<DT><B>Parameters</B>
<DD><code>statement</code> - statememt descriptor returned by <A HREF="#cli_statement"><code>cli_statement</code></A>
<DD><code>column_name</code> - zero terminated string with column name  
<DD><code>var_type</code> - type of variable as described in cli_var_type enum
<DD><code>var_ptr</code> - pointer to the variable
<DD><code>set</code> - function which will be called to construct fetched field. 
It receives pointer to the variable, length of the fetched array and returns pointer 
to the array's elements.
<DD><code>get</code> - function which will be called to update the field in the 
database. Given pointer to the variable, it should return pointer to the array elements 
and store length of the array to the variable pointer by len parameter
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<A NAME = "cli_array_column_ex"><pre>
typedef void* (*cli_column_set_ex)(int var_type, void* var_ptr, int len, 
				   char const* column_name, int statement, void const* data_ptr);
typedef void* (*cli_column_get_ex)(int var_type, void* var_ptr, int* len, 
				   char const* column_name, int statemen);

int cli_array_column(int               statement,
		     char const*       column_name, 
		     int               var_type,
		     void*             var_ptr,
		     cli_column_set_ex set,
		     cli_column_get_ex get);
</pre></A>
<DL><DD>
Specify extended get/set functions for the array column
<DL>
<DT><B>Parameters</B>
<DD><code>statement</code> - statememt descriptor returned by <A HREF="#cli_statement"><code>cli_statement</code></A>
<DD><code>column_name</code> - zero terminated string with column name  
<DD><code>var_type</code> - type of variable as described in cli_var_type enum
<DD><code>var_ptr</code> - pointer to the variable
<DD><code>set</code> - function which will be called to construct fetched field. 
It receives type of the vartiable, pointer to the variable, length of the fetched array, name of the fetched column,
statement descriptor and pointer to the array data. If this method returns not NULL pointer, 
database will copy unpacked array to the returned location. Otherwise it is assumed that
function handle data itself.
<DD><code>get</code> - function which will be called to update the field in the 
database. Given type of the vartiable, pointer to the variable, column name and statment descriptor,
it should return pointer to the array elements and store length of the array to the variable pointer by len parameter
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

    
<A NAME = "cli_fetch"><pre>
enum { 
    cli_view_only, 
    cli_for_update
};

int cli_fetch(int statement, int for_update);
</pre></A>
<DL><DD>
Execute select statement.
<DL>
<DT><B>Parameters</B>
<DD><code>statement</code> - statememt descriptor returned by <A HREF="#cli_statement"><code>cli_statement</code></A>
<DD><code>for_update</code> - not zero if fetched rows will be updated 
<DT><B>Returns</B>
<DD><code>&gt;= 0</code> - success, for select statements number of fetched rows is returned
<DD><code>&lt;  0</code> - error code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<A NAME = "cli_insert"><pre>
int cli_insert(int statement, cli_oid_t* oid);
</pre></A>
<DL><DD>
Execute insert statement.
<DL>
<DT><B>Parameters</B>
<DD><code>statement</code> - statememt descriptor returned by <A HREF="#cli_statement"><code>cli_statement</code></A>
<DD><code>oid</code> - object identifier of created record. 
<DT><B>Returns</B>
<DD>status code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>


<A NAME = "cli_get_first"><pre>
int cli_get_first(int statement);
</pre></A>
<DL><DD>
Get first row of the selection.
<DL>
<DT><B>Parameters</B>
<DD><code>statement</code> - statememt descriptor returned by <A HREF="#cli_statement"><code>cli_statement</code></A>
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>


<A NAME = "cli_get_last"><pre>
int cli_get_last(int statement);
</pre></A>
<DL><DD>
Get last row of the selection.
<DL>
<DT><B>Parameters</B>
<DD><code>statement</code> - statememt descriptor returned by <A HREF="#cli_statement"><code>cli_statement</code></A>
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>


<A NAME = "cli_get_next"><pre>
int cli_get_next(int statement);
</pre></A>
<DL><DD>
Get next row of the selecteion. If get_next records is called exactly after 
<A HREF="#cli_fetch"><code>cli_fetch</code></A> function call, is will fetch the first record in selection.
<DL>
<DT><B>Parameters</B>
<DD><code>statement</code> - statememt descriptor returned by <A HREF="#cli_statement"><code>cli_statement</code></A>
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>


<A NAME = "cli_get_prev"><pre>
int cli_get_prev(int statement);
</pre></A>
<DL><DD>
Get previous row of the selecteion. If get_next records is called exactly after 
<A HREF="#cli_fetch"><code>cli_fetch</code></A> function call, is will fetch the last record  in selection.
<DL>
<DT><B>Parameters</B>
<DD><code>statement</code> - statememt descriptor returned by <A HREF="#cli_statement"><code>cli_statement</code></A>
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>


<A NAME = "cli_get_oid"><pre>
cli_oid_t cli_get_oid(int statement);
</pre></A>
<DL><DD>
Get object identifier of the current record
<DL>
<DT><B>Parameters</B>
<DD><code>statement</code> - statememt descriptor returned by <A HREF="#cli_statement"><code>cli_statement</code></A>
<DT><B>Returns</B>
<DD>object identifier or 0 if no object is seleected
</DL></DL>

<HR>


<A NAME = "cli_update"><pre>
int cli_update(int statement);
</pre></A>
<DL><DD>
Update the current row in the selection. You have to set
for_update parameter of <A HREF="#cli_fetch"><code>cli_fetch</code></A> to 1 in order to be able 
to perform updates. Updated value of row fields will be taken
from bound column variables. 
<DL>
<DT><B>Parameters</B>
<DD><code>statement</code> - statememt descriptor returned by <A HREF="#cli_statement"><code>cli_statement</code></A>
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>


<A NAME = "cli_remove"><pre>
int cli_remove(int statement);
</pre></A>
<DL><DD>
Remove all selected records. You have to set <code>for_update</code> parameter of 
<A HREF="#cli_fetch"><code>cli_fetch</code></A> to 1 in order to be able to remove records. 
<DL>
<DT><B>Parameters</B>
<DD><code>statement</code> - statememt descriptor returned by <A HREF="#cli_statement"><code>cli_statement</code></A>
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<A NAME = "cli_close_cursor"><pre>
int cli_close_cursor(int statement);
</pre></A>
<DL><DD>
Close current cursor
<DL>
<DT><B>Parameters</B>
<DD><code>statement</code> - statement descriptor returned by <A HREF="#cli_statement"><code>cli_statement</code></A>
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<A NAME = "cli_free"><pre>
int cli_free(int statement);
</pre></A>
<DL><DD>
Deallocate statement and all associated data
<DL>
<DT><B>Parameters</B>
<DD><code>statement</code> - statememt descriptor returned by <A HREF="#cli_statement"><code>cli_statement</code></A>  
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<A NAME = "cli_commit"><pre>
int cli_commit(int session);
</pre></A>
<DL><DD>
Commit current database transaction
<DL>
<DT><B>Parameters</B>
<DD><code>session</code> - session descriptor as returned by <A HREF="#cli_open"><code>cli_open</code></A>
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<A NAME = "cli_abort"><pre>
int cli_abort(int session);
</pre></A>
<DL><DD>
Abort current database transaction
<DL>
<DT><B>Parameters</B>
<DD><code>session</code> - session descriptor as returned by <A HREF="#cli_open"><code>cli_open</code></A>
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<A NAME = "cli_show_tables"><pre>
int cli_show_tables(int session, cli_table_descriptor** tables);
</pre></A>
<DL><DD>
Return list of table presetn in the database.
<PRE> 
        typedef struct cli_table_descriptor {
            char const*       name;
        } cli_table_descriptor;
</PRE>
<DL>
<DT><B>Parameters</B>
<DD><code>session</code> - session descriptor as returned by <A HREF="#cli_open"><code>cli_open</code></A>
<DD><code>tables</code> - address of the pointer to the array with table descriptors. 
<code>cli_show_tables</code> uses malloc to allocate this array, and it should be deallocated by application using free() function.
<DT><B>Returns</B>
<DD><code>&gt;= 0</code> - number of tables in the database (Metatable is not returned/counted)
<DD><code>&lt;  0</code> - error code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<A NAME = "cli_describe"><pre>
int cli_describe(int session, char const* table, cli_field_descriptor** fields);
</pre></A>
<DL><DD>
Return definition of fields of specified table. Definition of field descriptor has the following format:
<PRE> 
        typedef struct cli_field_descriptor {  
            enum cli_var_type type;
            char const*       name;
        } cli_field_descriptor;
</PRE>
<DL>
<DT><B>Parameters</B>
<DD><code>session</code> - session descriptor as returned by <A HREF="#cli_open"><code>cli_open</code></A>
<DD><code>table</code> - name of the table
<DD><code>fields</code> - address of the pointer to the array with field descriptors. <code>cli_describe</code> uses malloc to allocate this array, and it should be deallocated by application using free() function.
<DT><B>Returns</B>
<DD><code>&gt;= 0</code> - number of fields in the table
<DD><code>&lt;  0</code> - error code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<A NAME = "cli_describe_layout"><pre>
int cli_describe_layout(int session, char const* table, cli_field_layout** fields, int* rec_size);
</pre></A>
<DL><DD>
Return layout of fields of specified table. Structure describing a field layout has the following format:
<PRE> 
        typedef struct cli_field_layout {
            cli_field_descriptor desc;
            int                  offs;
            int                  size;
        } cli_field_layout;
</PRE>
<DL>
<DT><B>Parameters</B>
<DD><code>session</code> - session descriptor as returned by <A HREF="#cli_open"><code>cli_open</code></A>
<DD><code>table</code> - name of the table
<DD><code>fields</code> - address of the pointer to the array with field layout descriptors. <code>cli_describe_layout</code> uses malloc to allocate this array, and it should be deallocated by application using free() function.
<DD><code>rec_size</code> - extracted record size (application can use this size to allocate buffer for cli_execute_query function)
<DT><B>Returns</B>
<DD><code>&gt;= 0</code> - number of fields in the table
<DD><code>&lt;  0</code> - error code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

A NAME = "cli_create_table"><pre>
int cli_create_table(int                   session, 
                     char const*         tableName, 
                     int                   nFields, 
		     cli_field_descriptor* fields);
</pre></A>
<DL><DD>
Create new table
<DL>
<DT><B>Parameters</B>
<DD><code>session</code> - session descriptor as returned by <A HREF="#cli_open"><code>cli_open</code></A>
<DD><code>tableName</code> - name of the created table
<DD><code>nFields</code> - number of columns in the table
<DD><code>fields</code> - array with table columns descriptors. Descriptor is has the following structure:
<PRE>
    enum cli_field_flags { 
        cli_hashed           = 1, /* field should be indexed usnig hash table */
        cli_indexed          = 2  /* field should be indexed using B-Tree */
    };

    typedef struct cli_field_descriptor { 
        enum cli_var_type type;
        int               flags;
        char const*     name;
        char const*     refTableName;
        char const*     inverseRefFieldName;
    } cli_field_descriptor;
</PRE>
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<A NAME = "cli_alter_table"><pre>
int cli_alter_table(int                   session, 
                     char_t const*         tableName, 
                     int                   nFields, 
		     cli_field_descriptor* fields);
</pre></A>
<DL><DD>
Change format of existed table
<DL>
<DT><B>Parameters</B>
<DD><code>session</code> - session descriptor as returned by <A HREF="#cli_open"><code>cli_open</code></A>
<DD><code>tableName</code> - name of the altered table
<DD><code>nFields</code> - number of columns in the table
<DD><code>fields</code> - array with table columns descriptors. Descriptor is has the following structure:
<PRE>
    enum cli_field_flags { 
        cli_hashed           = 1, /* field should be indexed usnig hash table */
        cli_indexed          = 2, /* field should be indexed using B-Tree */
        cli_case_insensitive = 4  /* index is case insensitive */
    };

    typedef struct cli_field_descriptor { 
        enum cli_var_type type;
        int               flags;
        char_t const*     name;
        char_t const*     refTableName;
        char_t const*     inverseRefFieldName;
    } cli_field_descriptor;
</PRE>
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<A NAME = "cli_drop_table"><pre>
int cli_drop_table(int                   session, 
	           char const*         tableName); 
</pre></A>
<DL><DD>
Drop table
<DL>
<DT><B>Parameters</B>
<DD><code>session</code> - session descriptor as returned by <A HREF="#cli_open"><code>cli_open</code></A>
<DD><code>tableName</code> - name of the created table
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>


<HR>

<A NAME = "cli_alter_index"><pre>
int cli_alter_index(int           session, 
	            char const* tableName 
		    char const* fieldName, 
		    int           newFlags); 
</pre></A>
<DL><DD>
Add or remove column index
<DL>
<DT><B>Parameters</B>
<DD><code>session</code> - session descriptor as returned by <A HREF="#cli_open"><code>cli_open</code></A>
<DD><code>tableName</code> - name of the created table
<DD><code>fieldName</code> - name of the field
<DD><code>newFlags</code> - new flags of the field, if index exists for this field, but is not specified in 
<code>newFlags</code> mask, then it will be removed; if index not exists, but is 
specified in <code>newFlags</code> mask, then it will be created.
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<A NAME = "cli_freeze"><pre>
int cli_freeze(int statement);
</pre></A>
<DL><DD>
Freeze cursor. Make it possible to reused cursor after commit of the current transaction.
<DL>
<DT><B>Parameters</B>
<DD><code>statement</code> - statememt descriptor returned by <A HREF="#cli_statement"><code>cli_statement</code></A>
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<A NAME = "cli_unfreeze"><pre>
int cli_unfreeze(int statement);
</pre></A>
<DL><DD>
Unfreeze cursor. Reuse previously frozen cursor.
<DL>
<DT><B>Parameters</B>
<DD><code>statement</code> - statememt descriptor returned by <A HREF="#cli_statement"><code>cli_statement</code></A>
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<A NAME = "cli_seek"><pre>
int cli_seek(int statement, cli_oid_t oid);
</pre></A>
<DL><DD>
Position cursor to the record with specified OID
</pre></A>
<DT><B>Parameters</B>
<DD><code>statement</code> - statememt descriptor returned by <A HREF="#cli_statement"><code>cli_statement</code></A>
<DD><code>oid</code> - object identifier of the record to which cursor should be positioned
<DT><B>Returns</B>
<DD><code>&gt;= 0</code> - success, position of the record in the selection
<DD><code>&lt;  0</code> - error code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<A NAME = "cli_skip"><pre>
int cli_skip(int statement, int n);
</pre></A>
<DL><DD>
Skip specified number of rows. 
</pre></A>
<DT><B>Parameters</B>
<DD><code>statement</code> - statememt descriptor returned by <A HREF="#cli_statement"><code>cli_statement</code></A>
<DD><code>n</code> -  number of objects to be skipped<BR><UL>
<LI>if <code>n</code> is positive, then this function has the same effect as executing cli_get_next() function <code>n</code> times.
<LI>if <code>n</code> is negative, then this function has the same effect as executing cli_get_prev() function <code>-n</code> times.
<LI>if <code>n</code> is zero, this method just reloads current record
</UL>
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<H2><A NAME = "localcli">Local implementation of CLI</A></H2>

Starting from version 2.47 FastDB provides local implementation of CLI interface. 
It means that now it is possible to access database directly from C application using CLI functions 
without starting separate server and socket communication overhead. 
Local implementation of CLI functions are included in main fastdb library.
So if you want to use remote CLI, link you application with <code>cli.lib</code> and if you want to
access database locally - link it with <code>fastdb.lib</code>.
To create local session you should use <code>cli_create</code> function instead of <code>cli_open</code>. 
Calling <code>cli_create</code> when your application is linked with <code>cli.lib</code> or 
<code>cli_open</code> when it is linked with <code>fastdb.lib</code> cause <code>cli_bad_address</code> 
error.<P>

<HR>

<A NAME = "cli_create"><pre>
int cli_create(char const* databaseName,
               char const* filePath,   
               unsigned    transactionCommitDelay, 
	       int         openAttr, 
	       size_t      initDatabaseSize,
               size_t      extensionQuantum,
               size_t      initIndexSize,
               size_t      fileSizeLimit);
</pre></A>
<DL><DD>
Create connection to the local database
<DL>
<DT><B>Parameters</B>
<DD><code>databaseName</code> - database name
<DD><code>filePath</code> - path to the database file
<DD><code>transactionCommitDelay</code> - transaction commit delay (specify 0 to disable)
<DD><code>openAttr</code> - mask of cli_open_attributes. You can specify combination of the following 
attributes:<BR>
<UL>
<LI><code>cli_open_default</code>
<LI><code>cli_open_readonly</code>
<LI><code>cli_open_truncate</code>
<LI><code>cli_open_concurrent</code>
</UL>
<DD><code>initDatabaseSize</code> - initial size of database
<DD><code>extensionQuantum</code> - database extension quantum
<DD><code>initIndexSize</code> - initial size of object index
<DD><code>fileSizeLimit</code> - limit for file size (0 - unlimited)
<DT><B>Returns</B>
<DD><code>&gt;= 0</code> - connection descriptor to be used in all other cli calls
<DD><code>&lt;  0</code> - error code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>


<HR>

<A NAME = "cli_create_replication_node"><pre>
int cli_create_replication_node(int         nodeId,
                                int         nServers,
                                char*       nodeNames[],
                                char const* databaseName, 
                                char const* filePath, 
                                int         openAttr, 
                                size_t      initDatabaseSize,
                                size_t      extensionQuantum,
                                size_t      initIndexSize,
                                size_t      fileSizeLimit);
</pre></A>
<DL><DD>
Create connection to the local database with support of replication
<DL>
<DT><B>Parameters</B>
<DD><code>nodeId</code> - node identifier: 0 <= nodeId < nServers
<DD><code>nServers</code> - number of replication nodes (primary + standby)
<DD><code>nodeNames</code> - array with URLs of the nodes (address:port)
<DD><code>databaseName</code> - database name
<DD><code>filePath</code> - path to the database file
<DD><code>openAttr</code> - mask of cli_open_attributes (to allow concurrent read access to replication node,
<code>cli_open_concurren</code> attribute should be set) 
<DD><code>initDatabaseSize</code> - initial size of database
<DD><code>extensionQuantum</code> - database extension quantum
<DD><code>initIndexSize</code> - initial size of object index
<DD><code>fileSizeLimit</code> - limit for file size (0 - unlimited)
<DT><B>Returns</B>
<DD><code>&gt;= 0</code> - connection descriptor to be used in all other cli calls
<DD><code>&lt;  0</code> - error code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>


<HR>

<A NAME = "cli_attach"><pre>
int cli_attach(int session);
</pre></A>
<DL><DD>
Attach thread to the database. Each thread except one opened the database should first
attach to the database before any access to the database, and detach after end of the work with database
<DL>
<DT><B>Parameters</B>
<DD><code>session</code> - session descriptor as returned by <A HREF="#cli_open"><code>cli_open</code></A>
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<A NAME = "cli_detach"><pre>
int cli_detach(int session, int detach_mode);
</pre></A>
<DL><DD>
Attach thread to the database. Each thread except one opened the database should first
attach to the database before any access to the database, and detach after end of the work with database
<DL>
<DT><B>Parameters</B>
<DD><code>session</code> - session descriptor as returned by <A HREF="#cli_open"><code>cli_open</code></A>
<DD><code>detach_mode</code> - bit mask representing detach mode
<PRE>
    enum cli_detach_mode {
        cli_commit_on_detach          = 1,
        cli_destroy_context_on_detach = 2
    };
</PRE>
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<A NAME = "cli_create_transaction_context"><pre>
typedef void* cli_transaction_context_t;
cli_transaction_context_t cli_create_transaction_context();
</pre></A>
<DL><DD>
Create new transaction xontext which can be used in cli_join_transaction function
<DL>
<DT><B>Returns</B>
<DD>created transaction context
</DL></DL>

<HR>

<A NAME = "cli_join_transaction"><pre>
int cli_join_transaction(int session, cli_transaction_context_t ctx);
</pre></A>
<DL><DD>
Associate current threads with specified transaction context,
It allows to share single transaction between multiple threads.
<DL>
<DT><B>Parameters</B>
<DD><code>session</code> - session descriptor as returned by <A HREF="#cli_open"><code>cli_open</code></A>
<DD><code>ctx</code> - transaction context created by  <A HREF="#cli_create_transaction_context">cli_create_transaction_context</A>
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<A NAME = "cli_remove_transaction_context"><pre>
void cli_remove_transaction_context(cli_transaction_context_t ctx);
</pre></A>
<DL><DD>
emove transaction context
<DL>
<DT><B>Parameters</B>
<DD><code>ctx</code> - transaction context created by  <A HREF="#cli_create_transaction_context">cli_create_transaction_context</A>
</DL></DL>

<HR>


<A NAME = "cli_get_database_state"><pre>
typedef struct cli_database_monitor {
    int n_readers;
    int n_writers;
    int n_blocked_readers;
    int n_blocked_writers;
    int n_users;
} cli_database_monitor;

int cli_get_database_state(int session, cli_database_monitor* monitor);
</pre></A>
<DL><DD>
Obtain information about current state of the database.

Attach thread to the database. Each thread except one opened the database should first
attach to the database before any access to the database, and detach after end of the work with database
<DL>
<DT><B>Parameters</B>
<DD><code>session</code> - session descriptor as returned by <A HREF="#cli_open"><code>cli_open</code></A>
<DD><code>monitor</code> - pointer to the monitor structure. The folloing fields are set:
<TABLE>
<TR><TD><code>n_readers</code></TD><TD>number of granted shared locks</TD></TR>
<TR><TD><code>n_writers</code></TD><TD>number of granted exclusive locks</TD></TR>
<TR><TD><code>n_blocked_reader</code></TD><TD>number of threads which shared lock request was blocked</TD></TR>
<TR><TD><code>n_blocked_writers</code></TD><TD>number of threads which exclusive lock request was blocked</TD></TR>
<TR><TD><code>n_users</code></TD><TD>number of processes openned the database</TD></TR>
</TABLE>
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>


<A NAME = "cli_prepare_query"><pre>
int cli_prepare_query(int session, char const* query);
</pre></A>
<DL><DD>
Prepare SubSQL query statement. 
<DL>
<DT><B>Parameters</B>
<DD><code>session</code> - session descriptor as returned by <A HREF="#cli_open"><code>cli_open</code></A>
<DD><code>query</code> - query string with optional parameters. Parameters are specified
as '%T' where T is one or two character code of parameter type using the same notation as in printf:
<TABLE>
<TR><TD>%d or %i</TD><TD>cli_int4_t</TD></TR>
<TR><TD>%f</TD><TD>cli_int8_t</TD></TR>
<TR><TD>%Li, %li, %ld or %Ld </TD><TD>cli_int8_t</TD></TR>
<TR><TD>%p</TD><TD>cli_oid_t</TD></TR>
<TR><TD>%s</TD><TD>char*</TD></TR>
</TABLE>
<DT><B>Returns</B>
<DD><code>&gt;= 0</code> - statement descriptor
<DD><code>&lt;  0</code> - error code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<A NAME = "cli_execute_query"><pre>
int cli_execute_query(int statement, int for_update, void* record_struct, ...)
</pre></A>
<DL><DD>
Execute query previously prepared by <A HREF="#cli_prepare_query">cli_prepare_query</A> with varying list of parameters.<BR>
It is assumed that format of the destination C structure matches format of the target database table. 
For scalar and reference types mapping is obvious: you should use correspondent <code>cli_</code> types
in declaring structure and table fields. For array types, you should use <code>cli_array_t</code>
structure. Strings should be represented as <code>char*</code> and programmer should not try to 
deallocate them or copy this pointer and access it outside context of the current record. 

<DL>
<DT><B>Parameters</B>
<DD><code>statement</code> - statement descriptor returned by <A HREF="#cli_prepare_query">cli_prepare_query</A>
<DD><code>for_update</code> - not zero if fetched rows will be updated 
<DD><code>record_struct</code> - structure to receive selected record fields.
<DD><code>...</code> - varying list of query parameters
</TABLE>
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<A NAME = "cli_execute_query_ex"><pre>
int cli_execute_query_ex(int statement, int for_update, void* record_struct, int n_params, int* param_types, void** param_values)
</pre></A>
<DL><DD>
Execute query previously prepared by <A HREF="#cli_prepare_query">cli_prepare_query</A> with parameters passed as array.<BR>
It is assumed that format of the destination C structure matches format of the target database table. 
For scalar and reference types mapping is obvious: you should use correspondent <code>cli_</code> types
in declaring structure and table fields. For array types, you should use <code>cli_array_t</code>
structure. Strings should be represented as <code>char*</code> and programmer should not try to 
deallocate them or copy this pointer and access it outside context of the current record. 

<DL>
<DT><B>Parameters</B>
<DD><code>statement</code> - statement descriptor returned by <A HREF="#cli_prepare_query">cli_prepare_query</A>
<DD><code>for_update</code> - not zero if fetched rows will be updated 
<DD><code>record_struct</code> - structure to receive selected record fields.
<DD><code>n_params</code> - number of parameters
<DD><code>param_types</code> - types of parameters (cli_var_type)
<DD><code>param_values</code> - array of pointers to parameter values
</TABLE>
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<A NAME = "cli_insert_struct"><pre>
int cli_insert_struct(int session, char const* table_name, void* record_struct, cli_oid_t* oid);
</pre></A>
<DL><DD>
Insert new record represented as C structure.<BR>
It is assumed that format of the destination C structure matches format of the target database table. 
For scalar and reference types mapping is obvious: you should use correspondent <code>cli_</code> types
in declaring structure and table fields. For array types, you should use <code>cli_array_t</code>
structure. Strings should be represented as <code>char*</code>.
<DL>
<DT><B>Parameters</B>
<DD><code>session</code> - session descriptor as returned by <A HREF="#cli_open"><code>cli_open</code></A>
<DD><code>table_name</code> - name of the destination table
<DD><code>record_struct</code> - structure specifying value of record fields
<DD><code>oid</code> - pointer to the location to receive OID of created record (may be NULL)
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<A NAME = "cli_xml_export"><pre>
int cli_xml_export(int session, FILE* out);
</pre></A>
<DL><DD>
Export database in XML format
<DL>
<DT><B>Parameters</B>
<DD><code>session</code> - session descriptor as returned by <A HREF="#cli_open"><code>cli_open</code></A>
<DD><code>out</code> - output stream
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>

<A NAME = "cli_xml_import"><pre>
int cli_xml_import(int session, FILE* in);
</pre></A>
<DL><DD>
Import data from XML stream
<DL>
<DT><B>Parameters</B>
<DD><code>session</code> - session descriptor as returned by <A HREF="#cli_open"><code>cli_open</code></A>
<DD><code>in</code> - input stream
<DT><B>Returns</B>
<DD>result code as described in <A HREF="#cli_errors"><code>cli_result_code</code></A> enum
</DL></DL>

<HR>




<H2> <A NAME = "advanced">Delayed transactions and online backup scheduler</A></H2>

FastDB supports ACID transactions. It means that after database is reported that transaction is committed,
it is guaranteed that database will be able to recover transaction in case of system fault
(except corruption of database image at hard disk). The only way to provide this feature on standard 
equipment (without non-volatile RAM for example) and under general-purpose operating systems 
(Windows, Unix, ...) is to perform synchronous write to the disk. "Synchronous" in this context means 
that operating system will not return control to the application until data will be really written to 
the disk. Unfortunately synchronous write is very time expensive operation - average disk access time 
is about 10ms, so it is hard to achieve performance more than 100 transactions per second.<P>

But in many cases it is acceptable to loose changes for few last seconds (but preserving consistency
of the database). With this assumption, database performance can be significantly increased.
FastDB provides "delayed transaction commit model" for such applications. When commit transaction delay
is non zero, database doesn't perform commit immediately, instead of it delay it for specified timeout.
After expiration of this timeout, transaction is normally committed, so it ensures that only changes
done within specified timeout can be lost in case of system crash.<P>

If thread, which has initiated delayed transaction, 
starts new transactions before delayed commit of transaction is performed, then
delayed commit operation is skipped. So FastDB is able to group several subsequent 
transactions performed by on client into the large single transaction. And it will greatly increase
performance, because it reduces number of synchronous writes and number created shadow pages (see section
<A HREF="#transaction">Transactions</A>).<P>

If some other client tries to start transaction before expiration of delayed commit timeout, then
FastDB force delayed commit to proceed and release resource for another thread. So concurrency is not
suffered from delayed commit.<P>

By default delayed commits are disabled (timeout is zero). You can sepcify commit delay 
parameter as second optional argument of <code>dbDatabase::open</code> method.
In <code>SubSQL</code> utility, it is possible to specify value of transaction commit
delay by setting <code>"FASTDB_COMMIT_DELAY"</code> environment variable (seconds).<P>

Transaction commit scheme used in FastDB guaranty recovery after software and hardware fault if
image of the database at the disk was not corrupted (all information which was written to the disk
can be correctly read). If for some reasons, database file is corrupted, then the only way to
recover database is use backup (hoping that it was performed not so long time ago).<P>

Backup can be done by just copying database file when database is offline.
Class <code>dbDatabase</code> provides backup method which is able to perform online backup, 
which doesn't require stopping of the database. It can be called at any time by programmer.
But going further, FastDB provides backup scheduler, which is able to perform backup automatically.
The only things needed - name of the backup file and interval of time between backups.<P>

The method <code>dbDatabase::scheduleBackup(char const* fileName, time_t period)</code> 
spawns separate thread which performs backups to the specified location with specified period (in seconds).
If <code>fileName</code> ends with "?" character, then data of backup initiation is appended to the file 
name, producing the unique file name. In this case all backup files are kept on the disk (it is 
responsibility of administrator to remove too old backup files or transfer them to another media).
Otherwise backup is performed to the file with <code>fileName + ".new"</code> name, and after completion
of backup, old backup file is removed and new file is renamed to <code>fileName</code>.
Also in last case, FastDB will check the creation date of the old backup file (if exists) and adjust
wait timeout in such way, that delta of time between backups will be equal to specified period
(so if database server is started only for 8 hours per day and backup period is 24 hours, then
backup will be performed each day, unlike scheme with uniquely generated backup file names). 
<P>

It is possible to schedule backup processing in <code>SubSQL</code> utility by setting 
<code>FASTDB_BACKUP_NAME</code> environment variable.
Period value is taken from <code>FASTDB_BACKUP_PERIOD</code> environment variable if specified, otherwise it 
is set to one day. To recover from backup it is enough to copy some of the backup files instead of
corrupted database file.<P>



<H2><A NAME = "replication">Fault tolerant support</A></H2>

Starting from 2.49 version FastDB provides optional fault tolerant support.
It is possible to start one primary (active) and several standby nodes so that
all changes made in the primary node will be replicated to standby node. 
If the primary node is crashed, one of the standby nodes becomes active
and start to play role of primary node. Once crashed node is restarted, 
it will perform recovery, synchronize its state with primary node
and start functioning as standby node. Nodes are connected by sockets
and intended to be located at different computers. Communications are assumed to be 
reliable.<P>

To be able to use fault tolerant support, you should rebuild FastDB
with <code>REPLICATION_SUPPORT</code> option. To switch it on, 
set <code>FAULT_TOLERANT</code> variable at the beginning of makefile to 1.
You should use class <code>dbReplicatedDatabase</code> instead of <code>dbDatabase</code>.
In parameters to <code>open</code> method, in addition to database name and file name, you should specify
identifier of this node (integer from <code>0</code> till <code>N-1</code>), array with addresses of 
all nodes (<code>hostname:port</code> pair) and number of nodes (<code>N</code>).
Then you should start the program at each of <code>N</code> nodes. Once all instances are started, 
node with <code>ID=0</code> becomes active (primary node). Open method returns <code>true</code>
at this instance. Other nodes are blocked in <code>open</code> method.
If primary node is crashed, one of standby nodes is activated (<code>open</code> method
returns <code>true</code>) and this instance continue execution.
If crashed instance is restarted, it will try to connect to all other servers, restore
it state and continue functioning as standby node, waiting for its chance to replace crashed primary node.
If primary node is normally terminated, <code>close</code> method of all standby nodes returns <code>false</code>.
<P>

In fault tolerant mode FastDB keeps two files: one with database itself and one with page update counters.
The file with page update counters is used for incremental recovery. When crashed node is restarted, 
it sends page counters it has to the primary node and receives back only those pages which 
were changed at primary node within this period of time (pages which timestamps are greater
than sent by recovered node).<P>

In replication mode application (at primary node) is not blocked during transaction commit until all 
changes are flushed to the disk. Modified pages are flushed to the disk asynchronously by separate thread.
This leads to significant improvement in performance. But if all nodes are crashed, 
database can be in inconsistent state. It possible to specify delay for 
flushing data to this disk: the larger delay is, the less overhead of disk IO we have. 
But in case of crash, larger amount of data can be required to be sent from primary node to perform
recovery.<P>

If all nodes are crashed, system administrator should
choose the node with the most recent version of database (sorry, it
can not be done automatically yet), and start application at this
node, but not at other nodes. After expiration of small timeout (5
seconds), it will report that it failed to connect to other node.
When connections to all specified nodes are failed, the program will
perform local recovery and starts as new active node. Then you can
start other nodes which will perform recovery from active node.<P>

It is possible to use fault tolerant model with diskless mode (<code>DISKLESS_CONFIGURATION</code> build option).
In this case no data is stored to the disk (nether database file, neither page update counter).
It is assumed that at least one of nodes is always alive. Until there is at least one online node, 
data will not be lost. When crashed node is recovered from crash, primary node sends complete snapshot of the 
database to it (incremental recovery is not possible because state of crashed node is lost). 
As far as in this case there no disk operations, performance can be very high and limited only by throughput of 
network.<P>

When replication node is started it tries to connect to all other nodes within some specified timeout.
If within this time no connection can be established, then node is assumed to be started autonomously
and start working as normal (non-replicated) database. If nodes has established connections with some other nodes, 
then one with the smallest ID is chosen as replication master. All other nodes are switched to stand-by mode
and wait for replication requests from the master. If content of the database at master and slave is different
(it is determined using page counters array), then master perform recovery of standby node, sending to it 
most recent versions of the pages. If master is crashed, then standby nodes select new master (node
with the smallest ID). All standby nodes are blocked in open method until one of the following things happens:
<OL>
<LI>Master is crashed and this node is selected as new master. In this case <code>open</code> method
returns <code>true</code>. 
<LI>Master normally close database. In this case <code>open</code> method at all replicated nodes returns
<code>false</code>.
</OL>
<p>

It is possible to perform read-only access to the replicated database from other applications.
In this case replicated node should be created using <code>dbReplicatedDatabase(dbDatabase::dbConcurrentUpdate)</code> 
constructor invocation. Other applications can access the same database using 
<code>dbDatabase(dbDatabase::dbConcurrentReadMode)</code> instance.<p>

Not all applications needs fault tolerance. Many applications are using replication just to increase scalability, but 
distributing load between several nodes. For such applications FastDB provides simplified replication model.
In this case there are two kind of nodes: readers and writers. Any of writer nodes can play role of replication master.
And readers node are just received replicated data from master and can not update database themselves.
The main difference with the replication model described above is that reader node can never become master and
<code>open</code> method in this node returns control immediately after connection has been established with master node.
Then reader node access database as normal read-only database application. Updates from master node are received
by separate thread. Reader node should be created using <code>dbReplicatedDatabase(dbDatabase::dbConcurrentRead)</code>
constructor. It should use exactly the same database schema (classes) as at master node. 
Database connection for reader nodes is not closed automatically when master closes connection - it remains opened
and application can still access database in read-only mode. Once master node is restarted, it establish connection
with all standby nodes and continue sending updates to them. If there are no reader nodes, then replication
model is equivalent to the fault tolerance model described above, and if there is single writers and one or more 
reader nodes, then it is classical master-slave replication.<p> 


You can test fault tolerant mode using <code>Guess</code> example. Been compiled with 
<code>-DREPLICATION_SUPPORT</code> this example illustrate cluster of three nodes (all addresses refer to the 
localhost, but you can certainly replace them with names of real hosts in your net). 
You should start three instances of <code>guess</code> application with parameters <code>0..2</code>.
When all instances is started, application wit parameter <code>0</code> starts normal user dialogue
(it is game: "Guess an animal"). If you emulate crash of this application by pressing <code>Crtl-C</code>, 
then one of standby nodes continue execution.<P>

More sophisticated modes of replication are illustrated by <code>testconc</code> example.
There are three replication nodes which are started using 
<code>testconc update N</code> command, where N is identifier of the node: 0, 1, 2.
After starting all these three nodes, them are connected to each other, node 0 becomes master and start update of the 
database, replicating changes to node 1 and 2. It is possible to start one or more inspectors - applications
which are connected to the replicated database in read-only mode (using <code>dbConcurrentRead</code> access type).
Inspector can be started using <code>testconc inspect N T</code>, where N is identifier of the replicated node to which 
inspector should be connected and T is number of inspection threads.<p>

The same <code>testconc</code> example can be used to illustrate simplified replication model. 
To test it please start one master: <code>testconc update 0</code> and two read-only replication nodes:
<code>testconc coinspect 1</code> and <code>testconc coinspect 2</code>. Please notice the difference with the scenario 
described above: is case of fault tolerance model there is normal replication node started using 
<code>testconc update N</code> command and read-only node (not involved i replication process) connected to the
same database: <code>testconc inspect N</code>. And in case of simplified master-slave replication, there
is read-only replication node, which can not become master (and so in case of original master's crash, nobody can play its
role), but application running at this node access replicated database as normal read-only application.<p>


<H2><A NAME = "optimization">Query optimization</A></H2>

The execution of queries, when all data is present in memory, is very fast,
compared with the time for query execution in a traditional RDBMS. But FastDB
even more increases the speed for query execution by applying several optimizations:
using indices, inverse references and query parallelization. The following 
sections supply more information about these optimizations.<P>

<H3><A NAME = "indices">Using indices in queries</A></H3>
Indices are a traditional approach for increasing RDBMS performance. FastDB
uses two types of indices: <A HREF="#hashtable">extensible hash table</A>
and <A HREF="#ttree">T-tree</A>. The first type provides the fastest way (with constant 
time in average) to access a record with a specified value of the key.
Whereas the T-tree, which is acombination of AVL-Tree and array, has the 
same role for a MMRDBMS as the B-Tree for a traditional RDBMS. It provides
search, insertion and deletion operations with guaranteed logarithmic
complexity (i.e.  the time for performing a search/insert/delete operation
for a table with <I>N</I> records is <I>C*log2(N)</I>, where <I>C</I> is
some constant). The T-tree is more suitable for a MMDBMS than a B-Tree, because the 
last one tries to minimize the number of page loads (which is an expensive 
operation in disk-based databases), while the T-tree tries to optimize the number of 
compare/move operations. The T-tree is the best type to use with range operations or 
when the order of records is significant.<P>

FastDB uses simple rules for applying indices, allowing a programmer to predict 
when an index and which one will be used. The check for 
index applicability is done during each query execution, so the decision 
can be made depending on the values of the operands. 
The following rules describe the algorithm of applying indices by FastDB:<P>

<UL>
<LI>The compiled condition expression is always inspected from left to right.
<LI>If the topmost expression is <B>AND</B> then try to apply an index to the
left part of the expression, using the right part as a filter.
<LI>If the topmost expression is <B>OR</B> and an index can be applied 
to the left part of the expression, then apply the index and test the right part
for the possibility to use indices. 
<LI>Otherwise, an index is applicable to the expression, when 
<OL>
   <LI> the topmost expression is a relational operation 
       (<code>= &lt; &gt; &lt;= &gt;= between like</code>)
   <LI> the type of operands is boolean, numeric, string or reference
   <LI> the right operand(s) of the expression is either a constant literal 
        or a C++ variable, and
   <LI> the left part is an indexed field of the record 
   <LI> the index is compatible with a relational operation
</OL>
</UL><P>    

Now we should make clear what the phrase <I>"index is compatible with operation"</I>
means and which type of index is used in each case. A hash table can be used when:<P>

<UL>
<LI>a comparison for equality <code>=</code> is used. 
<LI>a <code>between</code> operation is used and the values of both bounds operands
are the same.
<LI>a <code>like</code> operation is used and the pattern string contains
no special characters ('%' or '_') and no escape characters (specified in an
<code>escape</code> part).
</UL><P>

A T-tree index can be applied if a hash table is not applicable (or a field
is not hashed) and:<P>

<UL>
<LI>a comparison operation (<code>= &lt; &gt; &lt;= &gt;= between</code>)
is used. 
<LI>a <code>like</code> operation is used and the pattern string contains
no empty prefix (i.e. the first character of the pattern is not '%' or '_').
</UL><P>

If an index is used to search the prefix of a <code>like</code> expression, and
the suffix is not just the '%' character, then an index search operation can return
more records than really match the pattern. In this case we should filter the
index search output by applying a pattern match operation.<P>

When the search condition is a disjunction of several subexpressions
(the expression contains several alternatives combined by the <code>or</code>
operator), then several indices can be used for the query execution. 
To avoid record duplicates in this case, a bitmap is used in the cursor
to mark records already selected.<P>

If the search condition requires a sequential table scan, the T-tree index 
still can be used if the <code>order by</code> clause contains the single 
record field for which the T-tree index is defined. As far as sorting is very 
expensive an operation, using an index instead of sorting significantly 
reduces the time for the query execution.<P>

It is possible to check which indices are used for the query execution,
and a number of probes can be done during index search, by compiling FastDB
with the option <code>-DDEBUG=DEBUG_TRACE</code>. In this case, FastDB will
dump trace information about database functionality including information
about indices.<P>

    
<H3><A NAME = "inverse">Inverse references</A></H3>
Inverse references provide an efficient and reliable way to establish
relations between tables. FastDB uses information about inverse references
when a record is inserted/updated/deleted and also for query optimization.
Relations between records can be of one of the following types:
<I>one-to-one, one-to-many</I> and <I>many-to-many</I>. 

<UL>
<LI>A <I>one-to-one</I> relation is represented by a reference field in the self and 
the target record.
<LI>A <I>one-to-many</I> relation is represented by a reference field in the self
record and an array of references field in the record of the target table.
<LI>A <I>many-to-one</I> relation is represented by an array of references field in 
the self record and a reference field in the record of the referenced table.
<LI>A <I>many-to-many</I> relation is represented by an array of references field in
the self and in the target record.
</OL><P>

When a record with declared relations is inserted in the table, the inverse
references in all tables, which are in relation with this record, are updated to
point to this record. When a record is updated and a field specifying the
record's relationship is changed, then the inverse references are also 
reconstructed automatically by removing references to the updated record
from those records which are no longer in relation with the updated record and by
setting inverse references to the updated record for new records included in the
relation. When a record is deleted from the table, references to it are 
removed from all inverse reference fields.<P>

Due to efficiency reasons, FastDB is not able to guarantee the consistency of 
all references. If you remove a record from the table, there still
can be references to the removed record in the database. Accessing these references 
can cause unpredictable behavior of the application and even database corruption.
Using inverse references allows to eliminate this problem, because
all references will be updated automatically and the consistency of references
is preserved.<P>


Let's use the following table definitions as an example:<P>

<PRE>
class Contract;

class Detail { 
  public:
    char const* name;
    char const* material;
    char const* color;
    real4       weight;

    dbArray&lt; dbReference&lt;Contract&gt; &gt; contracts;

    TYPE_DESCRIPTOR((KEY(name, INDEXED|HASHED), 
		     KEY(material, HASHED), 
		     KEY(color, HASHED),
		     KEY(weight, INDEXED),
		     RELATION(contracts, detail)));
};

class Supplier { 
  public:
    char const* company;
    char const* location;
    bool        foreign;

    dbArray&lt; dbReference&lt;Contract&gt; &gt; contracts;

    TYPE_DESCRIPTOR((KEY(company, INDEXED|HASHED), 
		     KEY(location, HASHED), 
		     FIELD(foreign),
		     RELATION(contracts, supplier)));
};


class Contract { 
  public:
    dbDateTime            delivery;
    int4                  quantity;
    int8                  price;
    dbReference&lt;Detail&gt;   detail;
    dbReference&lt;Supplier&gt; supplier;

    TYPE_DESCRIPTOR((KEY(delivery, HASHED|INDEXED), 
		     KEY(quantity, INDEXED), 
		     KEY(price, INDEXED),
		     RELATION(detail, contracts),
		     RELATION(supplier, contracts)));
};
</PRE><P>

In this example there are one-to-many relations between the tables
Detail-Contract and Supplier-Contract. When a <code>Contract</code>
record is inserted in the database, it is necessary only to set the references 
<code>detail</code> and <code>supplier</code> to the correspondent 
records of the <code>Detail</code> and the <code>Supplier</code> table. 
The inverse references <code>contracts</code> in these records will be updated 
automatically. The same happens when a <code>Contract</code> record is 
removed: references to the removed record will be automatically excluded
from the <code>contracts</code> field of the referenced <code>Detail</code> and 
<code>Supplier</code> records.<P>

Moreover, using inverse reference allows to choose more effective plans for query
execution. Consider the following query, selecting all details
shipped by some company:<P>

<PRE>
    q = "exists i:(contracts[i].supplier.company=",company,")";
</PRE>

The straightforward approach to execute this query is scanning the
<code>Detail</code> table and testing each record for this condition.
But using inverse references we can choose another approach: perform an
index search in the <code>Supplier</code> table for records with the specified
company name and then use the inverse references to locate records from the
<code>Detail</code> table, which are in transitive relation with the
selected supplier records. Certainly we should eliminate duplicates of
records, which can appear because the company can ship a number of different 
details. This is done by a bitmap in the cursor object.
As far as index search is significantly faster than sequential search
and accessing records by reference is very fast an operation, the total
time of such query execution is much shorter compared with the
straightforward approach.<P>

Starting from 1.20 version FastDB supports cascade deletes.
If field is declared using OWNER macro, the record is treated as owner of 
the hierarchical relation. When the owner records is removed all 
members of this relation (records referenced from the owner) will be 
automatically removed. If member record of the relation should contain
reference to the owner record, this field should be declared using
RELATION macro.<P>
  

<H3><A NAME = "realtime">Realtime issues</A></H3>
FastDB is not a true realtime system, because it is based on non-realtime 
operating systems (like NT or Unix), which mostly doesn't fit realtime 
requirements. 
But with some restrictions it is possible to give quite precise estimations
for query execution time in FastDB. Such restrictions include:<P>

<OL>
<LI>The whole database is in the physical memory and no swapping can take place
during application work.
<LI>Other applications should not consume much CPU time and system resources
(especially memory), to minimize the influence on the main application.
<LI>The required time of reaction is significantly longer than the quantum of 
processes rescheduling in the operating system. 
</OL><P>

Algorithms used in FastDB allow to quite precisely calculate the
average and maximal time of query execution depending on the number of records
in the table (assuming that the size of array fields in records is
significantly smaller than the table size; and the time of iteration through
array elements can be excluded from the estimation).
The following table shows the complexity of searching a table with
<I>N</I> records depending on the search condition:<P>

<TABLE BORDER ALIGN="center">
<TR><TH>Type of search</TH><TH>Average</TH><TH>Maximal</TH></TR>
<TR><TD>Sequential search</TD><TD ALIGN="center">O(N)</TD><TD ALIGN="center">O(N)</TD></TR>
<TR><TD>Sequential search with sorting</TD><TD ALIGN="center">O(N*log(N))</TD><TD ALIGN="center">O(N*log(N))</TD></TR>
<TR><TD>Search using hash table</TD><TD ALIGN="center">O(1)</TD><TD ALIGN="center">O(N)</TD></TR>
<TR><TD>Search using T-tree</TD><TD ALIGN="center">O(log(N))</TD><TD ALIGN="center">O(log(N))</TD></TR>
<TR><TD>Access by reference</TD><TD ALIGN="center">O(1)</TD><TD ALIGN="center">O(1)</TD></TR>
</TABLE><P>

FastDB uses the Heapsort algorithm for sorting selected records to provide
guaranteed log(N) complexity (quicksort is on the average a little bit faster,
but worst time is O(N*N)). A hash table also has different average and maximal
complexity. On the average, a hash table search is faster than a T-tree search, 
but in the worst case it is equivalent to a
sequential search while a T-tree search always guarantees log(N) complexity.<P>

The execution of update statements in FastDB is also fast, but this
time is less predictable, because the commit operation requires flushing of modified pages 
to disk which can cause unpredictable operating system delays.<P>



<H3><A NAME = "par">Parallel query execution</A></H3>

FastDB is able to split a query into several parallel jobs, which will be 
executed without any contention with each other. Parallelization of a query
is done by FastDB only for sequential scans of the table. In this case,
splitting jobs between <I>N</I> processors can reduce the query execution
time about <I>N</I> times (even more if the result shall be sorted).<P>

To split a table scan, FastDB starts <I>N</I> threads, each of them
tests <I>N</I>-s records of the table (i.e. thread number 0 tests records
<I>0,N,2*N</I>,... thread number 1 test records <I>1,1+N,1+2*N</I>,... and so on).
Each thread builds its own list 
of selected records. After termination of all threads, these lists
are concatenated to construct the single result list.<P>

If the result shall be sorted, then each thread, after finishing the table scan, 
sorts the records it selected. After termination of all threads,
their lists are merged (as it is done with an external sort).<P>

Parallel query execution is controlled by two parameters: the number of spawned
threads and a parallel search threshold. The first is specified in the
<code>dbDatabase</code> class constructor or set by the
<code>dbDatabase::setConcurrency</code> method. A zero value of this parameter 
asks FastDB to automatically detect the number of online CPUs in the system and 
spawns exactly this number of threads. By default, the number of threads is set to 1,
so no parallel query execution takes place.<P>

The parallel search threshold parameter specifies the minimal number of records in the 
table for which parallelization of the query can improve query performance 
(starting a thread has its own overhead). This parameter is a static
component of the <code>dbDatabase</code> class and can be changed by an application at
any moment of time.<P> 

Parallel query execution is not possible when:<P>

<OL>
<LI>Indices are used for query execution.
<LI>The number of records in the table is less than <code>dbDatabase::dbParallelScanThreshold</code>.
<LI>A selection limit is set for the cursor.
<LI>The query includes a <code>start from</code> part.
</OL><P>




<H2> <A NAME = "gist">Generalized search tree</A></H2>

In addition to built-in B-Tree and R-Tree indices, FastDB makes it possible
for programmer to define their own indices. FastDB provides interface to GiST - Generalized
Search Tree. It is not integrated in FastDB query mechanism, but rather provides
yet another way to select FastDB objects. FastDB uses GiST C++ library from University of 
California. FastDB provides implementation of <code>GiSTstore</code> interface which is 
responsible for storing/retrieving GiST pages in database. FastDB includes
release 0.9 beta 1 of the GiST C++ library with additional <code>GiSTdb.cpp</code> and 
<code>GiSTdb.h</code> files and changed BTree, RTree and RSTree examples, patched to work
with FastDB instead of plain fails.<P>
<A HREF="GiST/doc/index.html">GiST documentation is available here</A>


<H2> <A NAME = "implementation">FastDB implementation issues</A></H2>

This section describes some aspects of the FastDB implementation. 
It is not necessary to read this section unless you want to know
more about FastDB internals.<P>

<H3> <A NAME = "memory">Memory allocation</A></H3>

Memory allocation is performed in FASTDB by bitmap. Memory is allocated in
chunks called allocation quantum. In the current version of FastDB, the size of an
allocation quantum is 16 byte, i.e. the size of all allocated objects is 
aligned on a 16 byte boundary. Each 16 byte quantum  of database memory is represented by 
one bit in the bitmap. To locate a hole of a requested size in the bitmap, FastDB 
sequentially searches the bitmap pages for a correspondent number of successively
cleared bits. FastDB use three arrays indexed by bitmap byte, which 
allows the fast calculation of the offset and the size of the hole within the byte.<P> 

FastDB performs a cyclic scan of bitmap pages. It saves the identifier
of the current bitmap page and the current position within the page. Each time 
an allocation request arrives, scanning the bitmap starts from the (saved)
current position.
When the last allocated bitmap page is scanned, scanning continues from the 
beginning (from the first bitmap page) upto the current position.
When no free space is found after a full cycle through all bitmap pages, 
a new bulk of memory is allocated. The size of the extension is the maximum of the size
of the allocated object and of the extension quantum. The extension quantum is a parameter
of the database, specified in the constructor. The bitmap is extended in order to map
the additional space. If the virtual space is exhausted and no more
bitmap pages can be allocated, then an <code>OutOfMemory</code> error
is reported.<P>

Allocating memory using a  bitmap provides high locality of references 
(objects are mostly allocated sequentially) and also minimizes
the number of modified pages. Minimizing the number of modified pages is 
significant when a commit operation is performed and all dirty pages should
be flushed onto the disk. When all cloned objects are placed sequentially,
the number of modified pages is minimal and the transaction commit time is
reduced. Using the extension quantum helps to
preserve sequential allocation. Once the bitmap is extended, objects will
be allocated sequentially until the extension quantum is completely consumed. 
Only after reaching the end of the bitmap, the scan restarts from the beginning,
searching for holes in previously allocated memory.<P>


To reduce the number of bitmap page scans, FastDB associates a descriptor with each
page, which is used to remember the maximal size of the hole in the page.
This calculation of the maximal hole size is performed in the following way:
if an  object of size <I>M</I> can not be allocated from this bitmap page, 
the maximal hole size is less than <I>M</I>, and <I>M</I>
is stored in the page descriptor if the previous size value of the descriptor is greater
than <I>M</I>. For the next allocation of an object of size
&gt;= <I>M</I>, we will skip this bitmap page. The page descriptor
is reset when some object is deallocated within this bitmap page.<P>

Some database objects 
(like hash table pages) should be aligned on the page boundary
to provide more efficient access. The FastDB memory  allocator checks the requested
size. If it is aligned on page boundary, the address of the
allocated memory segment is also aligned on page boundary. A search for a free hole
will be done faster in this case, because FastDB increases the step of the current 
position increment according to the value of the alignment.<P>

To be able to deallocate memory used by an object, FastDB needs to keep somewhere
information about the object size. There are two ways of getting the object size in 
FastDB. All table records are prepended by a record header, which contains the
record size and a (L2-list) pointer, linking all records in the table. 
Such the size of the table record object can be extracted from the record header.
Internal database objects (bitmap pages, T-tree and hash table nodes)
have known size and are allocated without any header. Instead of this,
handles for such objects contain special markers, which allow to determine the
class of the object and get its size from the table of builtin object sizes.
It is possible to use markers because allocation is always done in quanta of
16 bytes, so the low 4 bits of an object handle are not used.<P>

It is possible to create a database larger than 4Gb or containing more than 
4Gb of objects, if you pass values greater than 32 bit in the compiler command line
for the <code>dbDatabaseOffsetBits</code> or the
<code>dbDatabaseOidBits</code> parameter.
In this case, FastDB will use an 8 byte integer type to
represent an object handle/object identifier. It will work only at truly 
64-bit operating systems, like Digital Unix.<P>


<H3> <A NAME = "transaction">Transactions</A></H3>

Each record (object) in FastDB has a unique identifier (OID). Object identifiers 
are used to implement references between objects. To locate an object by 
reference, its OID is used as an index of an array (of object offsets within the file).
This array is called <I>object index</I>, an element of this array is a an
<I>object handle</I>. There exist two object 
indices in FastDB, one of which is the current and the other the shadow. 
The header of the database contains pointers to both object indices and an indicator
to decide which index is the current at this moment.<P>

When an object is modified the first time, it is cloned 
(a copy of the object is created) and the object handle in the current index is
changed to point to the newly created object copy. The shadow index still
contains a handle which points to the original version of the object. 
All changes are done with the object copy, leaving the original object unchanged. 
FastDB marks in a special bitmap page of the object index, which one contains 
the modified object handle.<P>

When a transaction is committed, FastDB first checks if the size of the object index
was increased during the commited transaction. If so, it also reallocates the shadow 
copy of the object index. Then FastDB frees memory for all "old objects", 
i.e. objects which has been cloned within the transaction. Memory can not be 
deallocated before commit, because we want to preserve the consistent 
state of the database by keeping cloned objects unchanged. 
If we deallocated memory immediately after cloning, a new object could be 
allocated at the place of the cloned object, and we would loose
consistency. As memory deallocation is done in FastDB by the bitmap
using the same transaction mechanism as for normal database objects, 
deallocation of object space will require clearing some bits in a bitmap page,
which also should be cloned before modification. Cloning a bitmap page will
require new space for allocation of the page copy, and we could reuse the space of 
deallocated objects. But this is not acceptable due to the reasons explained 
above - we will loose database consistency. That is why deallocation 
of object is done in two steps. When an object is cloned, all bitmap pages
used for marking the object space, are also cloned (if 
not cloned before). So when the transaction is committed, we only clear some bits in 
bitmap pages: no more requests for allocation of memory can be generated at 
this moment.<P>

After deallocation of old copies, FastDB flushes all modified pages onto the disk 
to synchronize the contents of the memory and the contents of the disk file.
After that, FastDB changes the current object index indicator in the database
header to switch the roles of the object indices. The current object index becomes the
shadow index and vice versa. Then FastDB again
flushes the modified page (i.e. the page with the database header) onto the disk, transferring 
the database to a new consistent state. 
After that, FastDB copies all modified handles from the new object index
to the object index which was previously shadow and now becomes current.
At this moment, the contents of both indices are synchronized and FastDB is ready 
to start a new transaction.<P>

The bitmap of the modified object index pages is used to minimize the duration of committing
a transaction. Not the whole object index, but only its modified pages should be 
copied. After the transaction commitment the bitmap is cleared.<P>

When a transaction is explicitly aborted by the <code>dbDatabase::rollback</code>
method, the shadow object index is copied back to the current index, eliminating
all changes done by the aborted transaction. After the end of copying,
both indices are identical again and the database state corresponds to the state
before the start of the aborted transaction.<P>

Allocation of object handles is done by a free handle list. The header of the list 
is also shadowed and the two instances of the list headers are stored in the database 
header. A switch between them is done in the same way as between the
object indices. When there are no more free elements in the list, FastDB 
allocates handles from the unused part of a new index. When there is no
more space in the index, it is reallocated. The object index is the only 
entity in the database which is not cloned on modification. Instead of this,
two copies of the object index are always used.<P>

There are some predefined OID values in FastDB. OID <I>0</I> is reserved
as an invalid object identifier. OID <I>1</I> is used as the identifier for the
metatable object -
the table containing descriptors of all other tables in the database. This table
is automatically constructed during the database initialization; descriptors of
all registered application classes are stored in this metatable.
OID starting from <I>2</I> are reserved for bitmap pages. 
The number of bitmap pages depends on the maximum virtual space of the database.
For 32 bit handles, the maximal virtual space is 4Gb. The number
of bitmap pages can be calculated, as this size divided by page size divided
by allocation quantum size divided by number of bits in the byte. For a
4 Gb virtual space, a 4 Kb page size and 16 byte allocation quantum, 8K
bitmap pages are required. So 8K handles are reserved in the object index for
bitmaps. Bitmap pages are allocated on demand, when the database size is extended. 
So the OID of the first user object will be 8194.<P>


<H3> <A NAME = "recovery">Recovery</A></H3>

The recovery procedure is trivial in FastDB. There are two instances of 
an object index, one of which is current and another corresponds to 
a consistent database state. When the database is opened, FastDB checks the database
header to detect if the database was normally closed. If not, 
i.e. if a <code>dirty</code> flag is set in the database header, FastDB performs a
database recovery. Recovery is very similar to rollback of transactions. 
The indicator of the current index in the database object header is used to 
determine the index corresponding to the consistent database state. Object handles 
from this index are copied to another object index, eliminating
all changes done by uncommitted transactions. As the only action
performed by the recovery procedure is copying the object index (really only
handles having different values in the current and the shadow index are copied to 
reduce the number of modified pages) and the size of the object index is small,
recovery can be done very fast. 
The fast recovery procedure reduces the "out-of-service" time for
an  application.<P>

There is one hack which is used in FastDB to increase the database performance. 
All records in the table are linked in an L2-list, allowing efficient traversal
through the list and insertion/removal of records. 
The header of the list is stored in a table object (which is the record of the
<code>Metatable</code>). L2-list pointers are 
stored at the beginning of the object together with the object size. 
New records are always appended in FastDB at the end of the list. 
To provide consistent inclusion into a database list, we should clone the last record
in the table and the table object itself. But if the record size is very big,
cloning the last record can cause significant space 
and time overhead.<P>

To eliminate this overhead, FastDB does not clone the last record but allows a
temporary inconsistency of the list. In which state will the list be if a
system fault happens before committing the transaction ? The consistent 
version of the table object will point to the record which was the last record in 
the previous consistent state of the database. But as this record was not 
cloned, it can contain pointers to a next record, which doesn't exist in this
consistent database state. To fix this inconsistency, FastDB checks all tables 
in the database during the recovery procedure: if the last record in the 
table contains a non-NULL <I>next</I> reference, <I>next</I> is changed to NULL to restore
consistency.<P>

If a database file was corrupted on the disk, the only way to recover the database
is to use a backup file (certainly if you do not forget to make it).
A backup file can be made by the interactive SQL utility using the <code>backup</code>
command; or by the  application using the  <code>dbDatabase::backup()</code> method.
Both create a snapshot of the database in a specified file (it can be the name of a 
device, a tape for example). As far as a database file is always in a consistent
state, the only action needed to perform recovery by means of the backup file
is to replace the original database file with the backup file.<P>

If some application starts a transaction, locks the database and then crashes, 
the database is left in a locked state and no other application can access it.
To restore from this situation, you should stop all applications working with 
the database. Then restart. The first application opening the database
will initialize the
database monitor and perform recovery after this type of crash.<P>


<H3> <A NAME = "hashtable">Hash table</A></H3>

Hash tables provide (in the average) the fastest way to locate a record in the table
by key. Depending on the hash table size and quality of the hash 
function, one or more probes will be needed to locate the record.
Hash tables are the best when most of the queries use equality comparison
for record fields.<P>

FastDB uses an extensible hash table with collision chains. 
The table is implemented as an array of object references with a pointer
to a collision chain. Collision chain elements form a L1-list:  each element 
contains a pointer to the next element, the hash function
value and the OID of the associated 
record. Hash tables can be created for boolean, numeric and string fields.<P> 

To prevent the growth of collision chains, the size of a hash table is
automatically increased when the table becomes full.
In the current implementation, the  hash table is extended when
both of the following two conditions are true:

<OL>
<LI>The number of records in the tables becomes greater than the hash table size.
<LI>The number of used elements in the hash table (i.e. number of non-empty collision
chains) is greater than 2/3 of the hash table size. 
</OL>

The first condition allows to located each element in the hash table using one
probe in average (certainly it depends on the distribution of key values and
on the hash function). The second condition prevents the hash table from growing when
the capacity of the set of possible key values becomes smaller then the hash table size
(for example, it does not make sense to extend a hash table used for hashing
<code>char</code> field, because no more than 256 items of the hash table can be 
used). Each time the hash table is extended, its size is doubled. More precisely:
the hash table size is <I>2**n-1</I>. 
Using an odd or a prime number for the hash size allows to improve the
quality of hashing and efficiently
allocates space for hash table, the size of which is aligned on page 
boundary. If the hash table size is <I>2**n</I>, than we will always loose
the least <I>n</I> bits of the hash key.<P>

FastDB uses a very simple hash function, which despite of its simplicity can
provide good results (uniformal distribution of values within the hash table).
The hash code is calculated using all bytes of the key value by the following formula:

<PRE>
        h = h*31 + *key++;
</PRE>

The hash table index is the remainder of dividing the hash code by the hash table size.<P>



<H3> <A NAME = "ttree">T-tree</A></H3>

In the article "A study of index structures for main memory database management
systems", T.J. Lehman and M.J Carey proposed the T-trees as a storage efficient data
structure for main memory databases. T-trees are based on AVL trees proposed
by Adelson-Velsky and Landis. In this subsection, we provide an overview of 
T-trees as implemented in FastDB.<P> 

Like AVL trees, the
height of left and right subtrees of a T-tree may differ by at most one.
Unlike AVL trees, each node in a T-tree stores multiple key values in a sorted
order, rather than
a single key value. The left-most and the right-most key value in a node
define the range of key values contained in the node. Thus, the left subtree
of a node contains only key values less than the left-most key value, while the
right subtree contains key values greater than the right-most key value in the
node. A key value which falls between the smallest and largest key value in
a node is said to be <I>bounded</I> by that node. 
Note that keys equal to the smallest
or largest key in the node may or may not be considered to be bounded based on
whether the index is unique and based on the search condition (e.g.
"greater-than" versus "greater-than or equal-to").<P>

A node with both a left and
a right child is referred to as an <I>internal node</I>, 
a node with only one child is referred to as a <I>semi-leaf</I>, 
and a node with no children is referred to as a <I>leaf</I>. 
In order to keep the occupancy high, every internal node must contain a minimum number
of key values (typically <I>k-2</I>, if <I>k</I>
is the maximum number
of keys that can be stored in a node). However, there is no occupancy condition
on the leaves or semi-leaves.<P>

Searching for a key value in a T-tree is
relatively straightforward. For every node, a check is made to see if the key
value is bounded by the left-most and the right-most key value in the node; if
this is the case, then the key value is returned if it is contained in the node
(else, the key value is not contained in the tree). Otherwise, if the key value
is less than the left-most key value, then the left child node is searched;
else the right child node is searched. The process is repeated until either the
key is found or the node to be searched is null.<P>

Insertions and deletions into
the T-tree are a bit more complicated. For insertions, first a variant of the
search described above is used to find the node that bounds the key value to
be inserted. If such a node exists, then if there is room in the node, the key
value is inserted into the node. If there is no room in the node, then the key
value is inserted into the node and the left-most key value in the node is
inserted into the left subtree of the node (if the left subtree is empty, then
a new node is allocated and the left-most key value is inserted into it). If no
bounding node is found, then let <I>N</I> be the last node encountered by the 
failed search and proceed as follows: If <I>N</I>
has room, the key value is inserted into <I>N</I>;
else, it is inserted into a new node that is either the right or left child of
<I>N</I>, depending on the key value and the left-most and right-most key 
values in 
<I>N</I>.<P>

Deletion of a key value begins by determining the node containing the key
value, and the key value is deleted from the node. If deleting the key value
results in an empty leaf node, then the node is deleted. If the deletion
results in an internal node or semi-leaf containing fewer than the minimum
number of key values, then the deficit is made up by moving the largest key in
the left subtree into the node, or by merging the node with its right child.
<P> 

In both insert and delete, allocation/deallocation of a node may cause the 
tree
to become unbalanced and rotations (RR, RL, LL, LR) may be necessary.
The heights of subtrees in the following description include
the effects of the insert or delete operation. In case of an insert, nodes along
the path from the newly allocated node to the root are examined until

<OL>
<LI>either a node for which the two subtrees have equal heights is found 
(in this case no rotation needs to be performed),
<LI>or a node for which the difference in
heights between the left and the right subtrees is more than one is found and a
single rotation involving the node is performed. 
</OL><P>

In the case of delete, nodes
along the path from the de-allocated node's parent to the root are examined
until a node is found whose subtrees' heights now differ by one. Furthermore,
every time a node whose subtrees' heights differ by more than one is
encountered, a rotation is performed. Note that de-allocation of a node may
result in multiple rotations.<P>


<H2> <A NAME = "subsql">Interactive SQL</A></H2>

The interactive SUBSQL utility allows to browse any FastDB database and to perform
some administration functions with it. Also import/export of data
from the database can be done by SUBSQL utility. The name SUBSQL was chosen
to express that only a subset of SQL is implemented by this utility.<P>


The following rules in BNF-like notation specifies the grammar of the
SUBSQL directives:<P>

<PRE>
<I>directive</I> ::= 
    <B>select</B> (<B>*</B>) <B>from</B> <I>table-name</I> <I>select-condition</I> <B>;</B>
  | <B>insert into</B> <I>table-name</I> <B>values</B> <I>values-list</I> <B>;</B>
  | <B>create index on</B> <B>on</B> <I>table-name.field-name</I> <B>;</B>
  | <B>create table</B> <I>table-name</I> <B>(</B><I>field-descriptor</I> {<B>,</B> <I>field-descriptor</I>}<B>)</B> <B>;</B>
  | <B>alter table</B> <I>table-name</I> <B>(</B><I>field-descriptor</I> {<B>,</B> <I>field-descriptor</I>}<B>)</B> <B>;</B>
  | <B>update</B> <I>table-name</I> <B>set</B> <I>field-name</I> <B>=</B> <I>expression</I> {<B>,</B> <I>field-name</I> <B>=</B> <I>expression</I>} <B>where</B> <I>condition</I> <B>;</B>
  | <B>drop index</B> <I>table-name.field-name</I> <B>;</B>
  | <B>drop table</B> <I>table-name</I>
  | <B>open</B> <I>database-name</I> ( <I>database-file-name</I> ) <B>;</B>
  | <B>delete from</B> <I>table-name</I>
  | <B>backup</B> <I>file-name</I>
  | <B>start server</B> <I>server-URL</I> <I>number-of-threads</I>
  | <B>stop server</B> <I>server-URL</I>
  | <B>start http server</B> <I>server-URL</I> 
  | <B>stop http server</B> <I>server-URL</I>
  | <B>export</B> <I>xml-file-name</I>
  | <B>import</B> <I>xml-file-name</I>
  | <B>commit</B>
  | <B>rollback</B>
  | <B>autocommit</B> (<B>on</B> | <B>off</B>)
  | <B>exit</B>
  | <B>show</B>
  | <B>help</B>

<I>table-name</I> ::= <I>identifier</I>
<I>values-list</I> ::= <I>tuple</I> { <B>,</B><I> tuple</I> }
<I>tuple</I> ::= <B>(</B> <I>value</I> { <B>,</B> value } <B>)</B>
<I>value</I> ::= <I>number</I> | <I>string</I> | <B>true</B> | <B>false</B> 
               | <I>tuple</I>
<I>index</I> ::= <B>index</B> | <B>hash</B>
<I>field-descriptor</I> ::= <I>field-name</I> <I>field-type</I> (<B>inverse</B> <I>field-name</I>)
<I>field-name</I> ::= <I>identifier</I> { <B>.</B> <I>identifier</I> }
<I>database-name</I> ::= <I>string</I>
<I>database-file-name</I> ::= <I>string</I>
<I>xml-file-name</I> ::= <I>string</I>
<I>file-name</I> ::= <I>string</I>
<I>server-URL</I> ::= <code>'HOST:PORT'</code>
</PRE><P>

SUBSQL automatically commits a read-only transaction after each 
select statement in order to release a shared database lock as soon as possible.
But all database modification operations should be explicitly committed
by a <code>commit</code> statement or undone by a <code>rollback</code>
statement. <code>open</code> opens a new database, wherase <code>exit</code> closes 
an open database (if it was opened), and so implicitly commits the last transaction. 
If a database file name was not
specified in the <code>open</code> statement, then a file name is constructed from
the database name by appending the <code>".fdb"</code> suffix.<P>

The <code>select</code> statement always prints all record fields. FastDB doesn't support
tuples: the result of the selection is always a set of objects (records).
The format of the select statement output is similar with the one accepted by the insert
statement (with the exception of reference fields). So it is possible to 
export/import a database table without references by means of the
<code>select/insert</code> directives of SUBSQL.<P>

The <code>select</code> statement prints references in the format 
<code>"#hexadecimal-number"</code>. But it is not possible to use this format
in the <code>insert</code> statement. As object references are represented 
in FastDB by internal object identifiers, a reference field can not be set in an
<code>insert</code> statement (an object inserted into the database will
be assigned a new OID, so it does not make sense to specify a reference field
in the <code>insert</code> statement). To ensure database reference consistency,
FastDB just ignores reference fields when new records are inserted into the table
with references. You should specify the value 0 at the place of reference fields.
If you omit the '*' symbol in the select statement, FastDB will output object 
identifiers of each selected record.<P>

It is mandatory to provide values for all record fields in an <code>insert</code>
statement; default values are not supported. Components of structures and
arrays should be enclosed in parentheses.<P>

It is not possible to create or drop indices and tables while other 
applications are working with the database. Such operations change 
the database scheme: after such modifications the state of other applications
will become incorrect. But the <code>delete</code> operation
doesn't change the database scheme. So it can be performed as a normal transaction,
when the database is concurrently used by several applications.
If SUBSQL hangs trying to execute some statement, then some other application
holds the lock on the database, preventing SUBSQL from accessing it.<P>

It is possible to specify mode of openning database by SubSQL.
It can be done by <code>SUBSQL_ACCESS_TYPE</code> environment variable
or <code>-access</code> command line option. The following values can be specified:
<TABLE BORDER>
<TR><TH WIDTH=30%>Value</TH><TH WIDTH=30%>Mode</TH><TH>Description</TH></TR>
<TR><TD><code>normal</code></TD><TD><code>dbDatabase::dbAllAccess</code></TD><TD>Read-write access</TD></TR>
<TR><TD><code>read-only</code></TD><TD><code>dbDatabase::dbReadOnly</code></TD><TD>Read only access</TD></TR>
<TR><TD><code>concurrent-update</code></TD><TD><code>dbDatabase::dbConcurrentUpdate</code></TD><TD>Used in conjunction with concurrent read mode</TD></TR>
<TR><TD><code>concurrent-read</code></TD><TD><code>dbDatabase::dbConcurrentUpdate</code></TD><TD>Read only mode used in conjunction with concurrent update mode. In this case reads can be executed concurrently with updates.</TD></TR>
</TABLE><P>

SubSQL can be used to start CLI and HTTP servers.
CLI server accept connections of clients using CLI protocol to access database.
Each client is server by separate thread. SubSQL maintains pool of thread, taking 
thread from the pool when client is attached and place thread back in the pool when 
client is disconnected.<P>

HTTP server is used to provide view-only access to the database from Web browsers.
Unlike CLI servers, only one instance of HTTP server can be started. 
To view main database page, just type in your Web browser URL which you have
specified in <code>start http server</code> command.<P>

Database can be exported as XML file using SubSQL <code>export</code> command.
This command cause dump of the whole database in XML format to the specified file according
to the following rules:
<UL>
<LI>Each record is represented by XML element with the same name as the table.
<LI>Each record contains <code>id</code> attribute which specified OID of the object.
<LI>Each record field is represented by the XML element with the same name as field.
<LI>Values of scalar types are printed as decimal integer or float numbers.
<LI>String literals are enclosed in <code>""</code>. All characters greater than 'z' or less then ' ' or
equal to '%' or '"' are printed as two hex digits prepended by '%': space character = "%20".
<LI>Raw binary types are represented by string where each byte is represented by '%' and two hex digits.
<LI>Reference types are represented by <code>&lt;ref id=OID/&gt;</code> element, where OID is object identifier of
referenced object.
<LI>Array is represented as sequence of <code>&lt;array-element&gt;</code> elements
<LI>Rectangle is represented by <code>&lt;rectangle&gt;</code> element with two <code>&lt;vertex&gt;</code>
subelements containing list of coordinate attributes.
</UL><P>

Produced XML file can be used to export data to other programs or for flexible restoring of database.
To be able to import data from XML file you should have all table created. In C++ application it is enough
to open and close database, then all described tables will be created. SubSQL <code>import</code>
command will import data from XML file, mapping OIDs of records specified in XML file to OIDs of created records. 
Such export/import sequence can be used to convert database to the new format.<P>

Lets say that you have database <i>"YourOldDatabase"</i> created by your application <i>YourOldApplication</i>
and you want to convert it to new format so it can be used by new version of your application: 
<i>YourNewApplication</i>. First Of all you need to initialize new database. To do it you should run
<i>YourNewApplication</i> and open/close database <i>"YourNewDatabase"</i> in it.
Then prepare two SubSQL command files:<P>

<DL>
<DT><code>export.sql</code>:
<DD><pre>
open 'YourOldDatabase';
export '-'
exit
</pre>
<DT><code>import.sql</code>:
<DD><pre>
open 'YourNewDatabase';
import '-'
exit
</pre>
</DL>

Convesion can be done using the following command:

<pre>
subsql export.xml | subsql import.xml
</pre>
<P>

To be able to print <code>dbDateTime</code> in SubSQL in readable form, you should 
define <code>SUBSQL_DATE_FORMAT</code> environment variable (for example '%c'). To get more information about 
date time formats see documentation of <code>strftime<code> function. If <code>SUBSQL_DATE_FORMAT</code> 
is not defined, <code>dbDateTime</code> structure will be printed as normal structure
with integer component. SubSQL doesn't currently allow convertion of date from string during insert or update operations.<P>



<H2><A NAME = "www">API for development Web applications</A></H2>

New version of FastDB provides API for developing WWW applications.
It is very easy to perform Web database publishing with FastDB.
FastDB  server can either communicate with standard WWW server by
means of CGI requests, or it can serve HTTP requests itself.<P>
Interaction with Web server is based on three-tier model:

<PRE>
    Web Server   -&gt;     CGI stub     -&gt;    FastDB application
             CGI call          local socket connection  
</PRE>

Using FastDB built-in HTTP server provides maximum performance, because in 
this no communication and process creation overhead takes place.
In both cases the same API for receiving and unpacking requests 
and constructing responses is used. So the same application 
can be used for interaction with external Web server as well as 
stand-alone HTTP server.<P>

FastDB application is request-driven program, receiving data from
HTML forms and dynamically generating result HTML page. Classes
<code>WWWapi</code> and <code>WWWconnection</code> provide simple and 
convenient interface for getting HTTP requests, constructing HTML page and 
sending reply back to WWW browser. Abstract class <code>WWWapi</code>
has two implementations: <code>CGIapi</code> and <code>HTTPapi</code>,
first of which implements protocol of interaction with Web server by means of 
CGI mechanism, and the second - protocol of direct serving HTTP requests.<P>

Built-in HTTP server is able to handle two types of requests - 
transfer HTML file find in place relative to the current working directory
in response to GET HTTP request and perform action specified by GET or POST
requests with parameters. Built-in HTTP server provides persistent connections -
server will not close connection with client immediately after sending 
response, instead of this connection will be kept during some specified 
interval of time. Also this built-in server supports concurrent requests 
processing by several threads of control. But starting of threads should
be performed by client application.<P>

Virtual method <code>WWWapi::connect(WWWconnection& con)</code>
accept clients connection (either from CGISTUB program of from WWW browser).
This method returns <code>true</code> if connection is established. 
In this case programmer should call 
<code>CGIapi::serve(WWWconnection& con)</code> to receive and handle client's
requests. This method return <code>false</code> if and only if handler
of request returns <code>false</code>. Even if request was not correctly
received or could not be handled, <code>true</code> is returned by 
<code>serve</code> method. The connection is always closed after return from
<code>serve</code> method. It is possible to start separate thread for 
exceution of each <code>server</code> method.<P>

To construct responce to the request special overloaded <code>&gt;&gt;</code>
operators are provided in <code>WWWconnection</code> class. First line of 
response should specify type of response body, for example:

<PRE>
Content-type: text/html\r\n\r\n
</PRE>

Two CR-LF character after this line separate HTTP header from the body.
Three encoding schemes can be used for constructing response body:

<OL>
<LI><B>TAG</B> - used for specifying HTML control elements. No conversion is
done for this encoding.
<LI><B>HTML</B> - with this encoding output characters which are special for 
HTML (&Ltd; &gt; &amp; &qout;) are replaced with special symbolic names 
(&qout;lt; &qout;gt; &qout;amp; &qout;qout;). 
<LI><B>URL</B> - used for specifying call parameters in URL format. 
Spaces are replaced with '+' character, all other special characters with
their hex code.
</OL>

To make switching between encoding more convenient, <code>WWWconnection</code>
class performs automatic switching between encodings. Initially <B>TAG</B>
encoding is always used. Then encodings are implicitly changed using the 
following rules:

<PRE>
              TAG  -&gt; HTML
              HTML -&gt; TAG
              URL  -&gt; TAG
</PRE>

It certainly possible to explicitly specify encoding for the next output 
operation by means of special <code>&lt;&lt;</code> operator, which accepts 
one of the following constants: <code>TAG, HTML, URL</code>.<P>

Information about HTML form slots values or request parameters can be obtained 
using <code>WWWconnection::get(char const* name, int n = 0)</code> method.
Optional second parameter is used only for getting value of selectors with
multiple selection allows option. If parameter with such name is not found, 
<code>NULL</code> is returned. There are some mandatory parameters 
which always should be present in all forms handled by FastDB:<P>

<TABLE BORDER>
<TR><TH>Parameter name</TH><TH>Parameter Description</TH></TR>
<TR><TD>socket</TD><TD>address of the server, used for constructing new links</TD></TR>
<TR><TD>page</TD><TD>symbolic name of the page, used for request dispatching</TD></TR>
<TR><TD>stub</TD><TD>name of CGI stub program always defined by API</TD></TR>
</TABLE><P>


<H2> <A NAME = "examples">Examples of FastDB applications</A></H2>

FastDB is shipped with some examples of database applications, which
can help you creating your own applications.<P>

<H3> <A NAME = "guess">Example: game "Guess an animal"</A></H3>
"Guess an animal" is very simple a program which uses a database to 
store the game tree. Having a very simple algorithm, this program shows some elements of "artificial intelligence". The more information you provide to this
game, the smarter will be its behavior.<P>  

This is an example of a "navigation-only" application - 
no queries are used in this application at all. All navigation between
records (objects) is done by means of references. Really, this application
is more suitable for object oriented databases, but I include it in FastDB 

<OL>
<LI>to illustrate how easy navigation by references can be done in FastDB,
<LI>because this program is some kind of "trade mark" which I use in all
my databases.
</OL><P>


<H3> <A NAME = "testdb">Example: various types of queries</A></H3>

This application illustrates the usage of various types of database queries
and the advantages of using inverse references. A classical Detail/Contract/Supplier
database schema is used in this example. Compare the number of lines in this 
file with the number of lines needed to implement this example using ODBC or 
other RDBMS C API.<P>

<H3> <A NAME = "testperf">Performance test</A></H3>

This test allows to receive some results about the FastDB performance for
all basic operations. This test inserts <I>N</I> records into a table, 
then performs searches using a T-tree and a hash table, then a sequential search and
a sequential search with sorting. It is possible to specify a level 
of query parallelization in the command line. By default no parallelization
is used. The following table contains results for some systems and
<I>N</I> = 1000000. Values in the table rows specify the number of milliseconds
consumed by the operation which is calculated by dividing the time returned
by the <code>testperf</code> program by the number of iterations.<P>

<TABLE BORDER>
<TR><TH>System</TH><TH>Number of CPUs</TH><TH>Number of threads</TH><TH>Insertion*)</TH><TH>Hash table search</TH><TH>T-tree search</TH><TH>Sequential search</TH><TH>Sequential search with sorting</TH></TR>
<TR><TD>Pentium-II 300, 128 Mb RAM, Windows NT</TD><TD>1</TD><TD>1</TD><TD>0.056</TD><TD>0.015</TD><TD>0.041</TD><TD>1 400</TD><TD>25 000</TD></TR>
<TR><TD>Pentium-II 333, 512 Mb RAM, Linux</TD><TD>1</TD><TD>1</TD><TD>0.052</TD><TD>0.016</TD><TD>0.045</TD><TD>1 600</TD><TD>33 000</TD></TR>
<TR><TD>Pentium-Pro 200, 128 Mb RAM, Windows NT</TD><TD>2</TD><TD>1</TD><TD>0.071</TD><TD>0.023</TD><TD>0.052</TD><TD>1 600</TD><TD>35 000</TD></TR>
<TR><TD>Pentium-Pro 200, 128 Mb RAM, Windows NT</TD><TD>2</TD><TD>2</TD><TD>0.071</TD><TD>0.023</TD><TD>0.052</TD><TD>1 800</TD><TD>23 000</TD></TR>
<TR><TD>AlphaServer 2100, 250 Mhz, 512 Mb RAM, Digital Unix</TD><TD>2</TD><TD>1</TD><TD>0.250</TD><TD>0.031</TD><TD>0.084</TD><TD>2 600</TD><TD>42 000</TD></TR>
<TR><TD>AlphaServer 2100, 250 Mhz, 512 Mb RAM, Digital Unix</TD><TD>2</TD><TD>2</TD><TD>0.250</TD><TD>0.031</TD><TD>0.084</TD><TD>1 600</TD><TD>23 000</TD></TR>
<TR><TD>AlphaStation, 500 Mhz, 256 Mb RAM, Digital Unix</TD><TD>2</TD><TD>1</TD><TD>0.128</TD><TD>0.010</TD><TD>0.039</TD><TD>1 300</TD><TD>36 000</TD></TR>
</TABLE><P>

*) doesn't include commit time<P>

It will be nice if you can run this test at some other platforms and send me
the results. I need to notice, that for <I>N</I> = 1000000 you need
at least 128Mb of memory, otherwise you will test the performance of your disk.


<H3><A NAME = "bugdb">Bug tracking database</A></H3>

Example "Bug tracking database" illustrates developing Web application
using FastDB and WWW API. It can be used either with any WWW server 
(for example Apache or Microsoft Personal Web Server) or with
built-in HTTP server. To compile BUGDB for interaction with external server, 
define macro <code>USE_EXTERNAL_HTTP_SERVER</code>. 
Database can be
accessed from any computer running some WWW browser. To build 
<code>bugdb</code> application in Unix you should specify <code>www</code>
target to make utility.<P>

To run this BUGDB with external WWW server you should first customize your 
WWW server.
It should be able to access <code>buglogin.htm</code> file and run
CGI script <code>cgistub</code>. Also user, under which CGI scripts will
be executed, should have enough permissions to establish connection with 
FastDB application (by sockets). It is better to run FastDB application and
FastDB CGI scripts under the same user. For example, I have changed the 
following variables in Apache configuration file:

<PRE>
httpd.conf:
        User konst
        Group users

access.conf:
        &lt;Directory /usr/konst/fastdb&gt;
        Options All
        AllowOverride All
        allow from all
        &lt;/Directory&gt;

        DocumentRoot /usr/konst/fastdb

srm.conf:
        ScriptAlias /cgi-bin/ /usr/konst/fastdb/
</PRE>

It is also possible not to change configuration of WWW server, but place 
<code>cgistub</code> and <code>bugdb</code> programs in standard CGI
script directory and change in the file <code>buglogin.htm</code> path to 
the <code>cgistub</code> program.
After preparing configuration files you should start WWW server.<P>

No configuration is needed when you are using built-in HTTP server.
Just make sure that user has enough permission to access port number 80
(default port for HTTP server). If some HTTP server is already started at your
computer, you should either stop it or specify another port for 
built-in HTTP server. In last case you also need to specify the same port
in the settings of WWW browser to make it possible to establish connection with
right HTTP server. Also do not forget to specify real name of your computer
in ACTION field of buglogin.htm file.<P>

After starting <code>bugdb</code> application itself you can visit
<code>buglogin.htm</code> page in WWW browser and start to work with 
BUGDB database. When database is initialized, "administrator" user is 
created in the database. First time you should login as administrator using
empty password. Than you can create some other users/engineers and 
change the password. BUGDB doesn't use secure protocol of passing passwords and
doesn't worry much about restricting access of users to the database.
So if you are going to use BUGDB in real life, you should first
think about protecting database from unauthorized access.<P>


<H3><A NAME = "clidb">Clients-Managers database</A></H3>

This yet another example of Web database publishing. This database
contains information about clients and managers. Each client and each manager belongs to 
some segment (department). Managers can make remarks on status of a client from the same 
segment to which manager belongs. Some managers has mini-administrator permissions and
they are allowed to edit/remove reports made by other managers. Information about 
segments and mangers is maintained by database administrator.<P>

As well as BUGDB, this Web database example can work either through CGI interface with
some external HTTP server or use built-in HTTP server (last one is significantly
more efficient than interaction through CGI scripts). Look 
<A HREF="#bugdb">previous section</A> for more information about configuration of 
HTTP server. Do not forget to specify real name of your computer
in ACTION field of clilogin.htm file.<P>

After starting <code>clidb</code> application itself you can visit
<code>clilogin.htm</code> page in WWW browser and start to work with 
CLIDB database. When database is initialized, "administrator" user is 
created in the database. This database allows to specify IP address for the manager from 
which this manager can login to the system. So user authentication is based on 
the name and host computer IP address. Value '*' allows user to login from any host.
If you specify wrong IP address for the administrator and so are not able to login to 
the database, you can invoke clidb as 

<PRE>
       clidb <socket-name> login_from_any_host       
</PRE>


CLIDB also can be considered as example of multithreaded Web database server.
There is special class QueueManager which can be used for maintaining pool of threads
and distributing user HTTP requests between these threads. If you recompile CLIDB 
application with USE_QUEUE_MANAGER option set,
then CLIDB will spawn 8 threads for handling HTTP requests. In this case persistent
connection with client's WWW browsers are established (so there is no
extra overhead for establishing connecting for each HTTP request).<P>



<H2><A NAME = "quick">Quick start</A></H2>

When you are developing an application for FastDB, you should first decide
which data and which classes you want to store in the database. Then you
should describe the format of the database tables. Section 
<A HREF="#table">Table</A> describes how to create type and table descriptors.
Do not forget to register table descriptors by the <code>REGISTER</code> macro
(it should be done in some implementation module). If you are going
to redefine the default FastDB error handler (for example, if you want to use 
a message window for reporting instead of <code>stderr</code>), you should 
define your own database class and derive it from <code>dbDatabase</code>.
You should create an instance of the database class and make it accessible to
all application modules.<P>

Before you can do something with your database, you should open it.
Checking the <code>dbDatabase::open()</code> return code, you can
find out, if the database was successfully opened. Errors during database
opening do not terminate the  application (but they are reported)
even with the default error handler.<P>

Once you are certain that the database is normally opened, you can start
to work with the database. If your application is multithreaded and several threads
will work with the same database, you should attach each thread to the
database by the <code>dbDatabase::attach</code> method. Before thread termination,
it should detach itself from the database by invoking the
<code>dbDatabase::detach()</code> method. If your application uses navigation
through database objects by references, you need some kind of root object
which can be located without any references. The best candidate for the root
object is the first record of the table. FastDB guarantees that new
records are always inserted at the end of the table. So the first table record
is also the oldest record in the table.<P>

To access database data, you should create a number of <code>dbQuery</code>
and <code>dbCursor</code> objects. If several threads are working with the
database, each thread should have its own instances of query and
cursor objects. Usually it is enough to have one cursor for each table
(or two if your application also can update table records). But in case
of nested queries, using several cursors may be needed.
Query objects are usually created for each type of queries. Query objects are 
used also for caching compiled queries, so it will be a good idea to
extend the life span of query variables (may be make them static).<P>

There are four main operations with database: insert, select, update, remove.
The first is done without using cursors, by means of the global overloaded
template function <code>insert</code>. Selection, updating and deleting of 
records is performed using cursors. To be able to modify a table you should
use a cursor for update. A cursor in FastDB is typed and contains an instance
of an object of the table class. The overloaded '<code>operator-&gt;</code>'
of the cursor can be used to access components of the current record
and also to update these components. The method <code>update</code>
copies data from the cursor's object to the current table record.
The cursor's method <code>remove</code> will remove the current cursor record,
the method <code>removeAllSelected</code> will remove all selected records and
the method <code>removeAll</code> will remove all records in the table.
Each transaction should be either committed by
the <code>dbDatabase::commit()</code> or aborted by 
the <code>dbDatabase::rollback()</code> method. A transaction is started 
automatically when the first select, insert or remove operation is executed.<P>

Before exiting from your application do not forget to close the database.
Also remember, that the method <code>dbDatabase::close()</code> will automatically
commit the last transaction, so if this is not what you want, then explicitly perform
a <code>dbDatabase::rollback</code> before exit.<P>

So a template for a FastDB application can look like this:
<PRE>
//
// Header file
//
#include "fastdb.h"

extern dbDatabase db; // create database object

class MyTable { 
    char const* someField;
    ...
  public:
    TYPE_DESCRIPTOR((FIELD(someField)));
};

//
// Implementation
//
REGISTER(MyTable);

int main() 
{ 
    if (db.open("mydatabase")) { 
        dbCursor&lt;MyTable&gt; cursor;
        dbQuery q;

	char value[bufSize];

	q = "someField=",value;
	gets(value);
	if (cursor.select(q) &gt; 0) { 
	    do { 
	        printf("%s\n", cursor-&gt;someField);
	    } while (cursor.next());
        }
	db.close();
	return EXIT_SUCCESS;
    } else { 
        return EXIT_FAILURE;
    }
}
</PRE>	

To compile a FastDB application you have to include the header file
<code>"fastdb.h"</code>. This header file includes other FastDB header files,
so make sure that the FastDB directory is in the compiler's include path. To 
link a FastDB application, you need the FastDB library (<code>"fastdb.lib"</code>
for Windows or <code>"libfastdb.a"</code> for Unix). You can either
specify the full path to this library or place it in some default
library catalog (for example <code>/usr/lib</code> for Unix).<P>

To build the FastDB library, just type <code>make</code> in the FastDB directory. 
There is no autoconfiguration utility included 
in the FastDB distribution. Most system dependent parts of the code are compiled using
conditional compilation. There are two makefiles in the FastDB distribution. 
One for MS Windows with MS Visual C++ (<code>makefile.mvc</code>) 
and another one for generic Unix with a gcc compiler(<code>makefile</code>). 
If you want to use Posix threads or some other compiler, you
should edit this makefile. 
There is also a <code>make.bat</code> file, which just spawns a
<code>nmake -f makefile.mvc</code> command.
The <code>install</code> target in the
Unix makefile will copy FastDB header files, the FastDB library and the subsql utility
to directories specified by the <code>INCSPATH, LIBSPATH</code> and
</code>BINSPATH</code> makefile variables correspondingly.
Default values of these variables are the following:

<PRE>
        INCSPATH=/usr/include 
        LIBSPATH=/usr/lib
        BINSPATH=/usr/bin
</PRE><P>

Once your application starts to work, you will be busy with
support and extension of your application. FastDB is able to perform
automatic schema evaluation for such cases as adding a new field to the table and
changing the type of a field. The programmer can also add new indices or remove
rarely used indices. The database trace can be switched on (by (re-)compiling the
FastDB library with the <code>-DDEBUG=DEBUG_TRACE</code> option) to 
perform analysis of database functionality and efficiency of using indices.<P>

The SUBSQL utility can be used for database browsing and inspection, performing
online backups, importing data to and exporting data from the database.
FastDB will perform automatic recovery after system or application crash;
you should not worry about it. The only thing you perhaps have to do manually 
is stopping all database applications if one of them crashes, leaving the
database blocked.<P> 

FastDB allows to declare queries as static variables.
But in this case destructors of these queries can be called <b>after</b> destructors of the static
objects from the FastDB library itself (because order of invoking destructors for different modules is 
not specified. To solve this problem, in FastDB some global objects are replaced with references.
As a result destructors are never called for these objects. But it leads to <i>memory leaks</i>
in application. These <i>memory leaks</i> can not actually cause some problems (like memory exhaustion), 
but it case warning in some memory-checking utilities. And many C++ programmers like to use such utilities 
to check if all emory is correctly deallocated. To avoid these warning for FastDB objects you can 
register with <code>atexit</code> system function static method <code>dbTableDescriptor::cleanup()</code>, 
which will delete <b>all</b> objects allocated by FastDB.<P>


<H2><A NAME = "dbsize">Reducing initial size of the database file</A></H2>
By default the initial size of empty database file is 4 megabyte. For some application it is desirable to reduce initial size of the database.
You can increase or decrease the initial database size by changing <code>dbDefaultInitDatabaseSize</code> 
parameter. Reducing the initial database size can only cause only additional database 
reallocations when the database is growing. Reallocation is expensive operation (it requires 
unmapping the file and mapping it to the new location, as a result the modified pages are 
first saved to the disk, and then has to be reloaded from the disk), so reducing number
of reallocations is significant. FastDB duplicates the virtual memory size used by the 
database during reallocation.<P>

By changing <code>dbDefaultInitDatabaseSize</code> you could not make database
file to become smaller than 1Mb. This is because of another parameter - 
<code>dbDefaultInitIndexSize</code>, which specify size of object index. 
Default value is 64k, each entry is 4 bytes long and there two instances of the index - 
primary and shadow. So only the index occupies 512k of memory. Another 512k is reserved for
storing data. So the initial size of the database can be reduced by decreasing
<code>dbDefaultInitIndexSize</code> parameter. But I do not recommend to do it, because
it is unlikely that there will be less than several thousands objects in the database.<P>



<H2><A NAME="diskless">Diskless configuration</A></H2>

Some application needs only query engine and do not need to store data to the disk 
(for example, applications for mobile devices). FastDB provides <I>diskless configuration</I>.
It is switched on by rebuilding FastDB with DISKLESS_CONFIGURATION option set in makefile.
In this case FastDB will not write any data to the disk. When application is started database
is always empty. Other application can be connected to the same database, concurrently accessing
the same data. Database exists until there is some application using it. When last application
closes database, memory mapped object is destructed and all data is lost.<P>

It is important to notice that unlike normal mode, FastDB is not able to extend database in diskless 
mode. To be able to reallocate memory mapped object (to extend its size), FastDB will have
to create somewhere (in memory) temporary buffer to hold all database data, copy all data to this buffer, 
destruct original memory mapping object, create new memory mapping object, copy data from buffer to the 
new memory mapping object and then destruct the buffer. So if database size was <code>N</code>,  then
reallocation requires <code>3*N</code> free memory and copying of all database data two times.
I think this is too large memory and CPU overhead.<P>

So in diskless mode it is necessary to specify maximal database size in the constructor of 
<code>dbDatabase</code> (<code>dbInitSize</code> parameter). Specifying large size will not cause
some significant system overhead, because physical pages will be in any case allocated on demand.
So it is not so difficult to avoid exhaustion of database size by specifying very large 
value in <code>dbInitSize</code> parameter). The only restriction is that specified size should not
be greater than size of virtual memory in the system (usually size of swap + physical memory).<P>

In addition to DISKLESS_CONFIGURATION switch, FastDB also provides additional
switches to control used OS API: <code>USE_POSIX_MMAP, USE_POSIX_SEMAPHORES, NO_MMAP</code>.
Use them only if mechanism used by FastDB by default doesn't work (or work inefficiently
at your system. Some of these switches and enables implicitly once you have
choose particular configuration. The following table summarize usage of these switches:
 
<TABLE border>
<TR><TH>Set macrors</TH><TH>Implies</TH><TH>Data file</TH><TH>Monitor</TH><TH>Description</TH></TR>
<TR><TD>USE_POSIX_MMAP=0</TD><TD>NO_MMAP=1</TD><TD>shmat</TD><TD>shmat</TD><TD>normal access to database without mmap</TR></TD>
<TR><TD>USE_POSIX_MMAP=1</TD><TD>&nbsp;</TD><TD>mmap</TD><TD>mmap</TD><TD>private process database</TD></TR>
<TR><TD>NO_MMAP</TD><TD>&nbsp;</TD><TD>malloc</TD><TD>shmat</TD><TD>normal access</TD></TR>
<TR><TD>DISKLESS_CONFIGURATION</TD><TD>USE_POSIX_MMAP=0</TD><TD>shmat</TD><TD>shmat</TD><TD>transient public database</TD></TR>
<TR><TD>DISKLESS_CONFIGURATION<BR>USE_POSIX_MMAP=1</TD><TD>&nbsp;</TD><TD>mmap</TD><TD>mmap</TD><TD>transient private database</TD></TR>
</TABLE><P>

All combinations not defined in this table are considered to be invalid.
Also it is not recommended to set these macros explicitly and use configuration switches 
(like DISKLESS_CONFIGURATION) instead.<P>

<H2><A NAME = "sharing">Sharing of classes between different databases</A></H2>

Starting from version 2.18, FastDB supports sharing of
classes between several databases. To use this feature you should:<P>

<OL>
<LI>Register classes using <code>REGISTER_UNASSIGNED</code> macro.
<LI>Path pointer to dbDatabase as first parameter of <code>dbCursor</code> constructor.
<LI>Method <code>insert</code> is now member of </code>dbDatabase</code> class (if 
C++ compiler doesn't support member templates, you should define 
<code>NO_MEMBER_TEMPLATES</code> macro and path pointer to database as first parameter).
</OL><P>

For examle:

<PRE>
    class MyClass {
        ...
    };
    REGISTER_UNASSIGNED(MyClass);
    dbDatabase* db;
    dbCursor&lt;MyClass&gt; cursor(db);
    MyClass rec;
    if (cursor.select(q) == 0) {
        db->insert(rec);
    }
</PRE>


<H2><A NAME = "distribution">Distribution terms</A></H2>
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the <A HREF="#Software">Software</A>), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:<P>

<A NAME="Software">
<B>
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
AUTHOR OF THIS SOFTWARE BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR 
IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
</B>
</A><P>

I will provide e-mail support and help you with development of 
FastDB applications.<P>
<HR>
<P ALIGN="CENTER"><A HREF="http://www.garret.ru/~knizhnik">
<B>Look for new version at my homepage</B></A><B> | </B>
<A HREF="mailto:knizhnik@garret.ru">
<B>E-Mail me about bugs and problems</B></A></P>
</BODY>
</HTML>
